Как я могу реализовать дерево в Python? Есть ли встроенные структуры данных в Python, как в Java?

Я пытаюсь построить общее дерево. Есть ли встроенные структуры данных в Python для реализации дерева?

13 Solutions collect form web for “Как я могу реализовать дерево в Python? Есть ли встроенные структуры данных в Python, как в Java?”

Python не обладает довольно широким спектром «встроенных» структур данных, как это делает Java. Однако, поскольку Python является динамическим, общее дерево легко создать. Например, двоичное дерево может быть:

class Tree(object): def __init__(self): self.left = None self.right = None self.data = None 

Вы можете использовать его следующим образом:

 root = Tree() root.data = "root" root.left = Tree() root.left.data = "left" root.right = Tree() root.right.data = "right" 

anytree

Я рекомендую https://pypi.python.org/pypi/anytree

пример

 from anytree import Node, RenderTree udo = Node("Udo") marc = Node("Marc", parent=udo) lian = Node("Lian", parent=marc) dan = Node("Dan", parent=udo) jet = Node("Jet", parent=dan) jan = Node("Jan", parent=dan) joe = Node("Joe", parent=dan) print(udo) Node('/Udo') print(joe) Node('/Udo/Dan/Joe') for pre, fill, node in RenderTree(udo): print("%s%s" % (pre, node.name)) Udo ├── Marc │ └── Lian └── Dan ├── Jet ├── Jan └── Joe print(dan.children) (Node('/Udo/Dan/Jet'), Node('/Udo/Dan/Jan'), Node('/Udo/Dan/Joe')) 

Особенности

anytree также обладает мощным API:

  • простое создание дерева
  • простая модификация дерева
  • итерация дерева предварительного заказа
  • итерация дерева после заказа
  • разрешить относительные и абсолютные пути узлов
  • идущих от одного узла к другому.
  • рендеринг дерева (см. пример выше)
  • узлы подключения / отсоединения

Общее дерево – это узел с нулевым или большим числом детей, каждый из которых является правильным (деревом). Это не то же самое, что бинарное дерево, они разные структуры данных, хотя обе имеют некоторую терминологию.

В Python нет встроенной структуры данных для генерических деревьев, но она легко реализуется с помощью классов.

 class Tree(object): "Generic tree node." def __init__(self, name='root', children=None): self.name = name self.children = [] if children is not None: for child in children: self.add_child(child) def __repr__(self): return self.name def add_child(self, node): assert isinstance(node, Tree) self.children.append(node) # * # /|\ # 1 2 + # / \ # 3 4 t = Tree('*', [Tree('1'), Tree('2'), Tree('+', [Tree('3'), Tree('4')])]) 

Можешь попробовать:

 from collections import defaultdict def tree(): return defaultdict(tree) users = tree() users['harold']['username'] = 'hrldcpr' users['handler']['username'] = 'matthandlersux' 

Как предлагается здесь: https://gist.github.com/2012250

Внутри нет деревьев, но вы можете легко построить их путем подклассификации типа узла из списка и написания методов обхода. Если вы сделаете это, я нашел bisect полезным.

Есть также много реализаций PyPi, которые вы можете просматривать.

Если я правильно помню, стандартная библиотека Python не включает структуры древовидных данных по той же причине, что и в библиотеке базового класса .NET: местность памяти уменьшается, что приводит к большему количеству промахов в кеше. На современных процессорах, как правило, быстрее просто принести большой кусок памяти в кеш, а структуры данных, богатые указателями, отрицают выгоду.

 class Node: """ Class Node """ def __init__(self, value): self.left = None self.data = value self.right = None class Tree: """ Class tree will provide a tree as well as utility functions. """ def createNode(self, data): """ Utility function to create a node. """ return Node(data) def insert(self, node , data): """ Insert function will insert a node into tree. Duplicate keys are not allowed. """ #if tree is empty , return a root node if node is None: return self.createNode(data) # if data is smaller than parent , insert it into left side if data < node.data: node.left = self.insert(node.left, data) elif data > node.data: node.right = self.insert(node.right, data) return node def search(self, node, data): """ Search function will search a node into tree. """ # if root is None or root is the search data. if node is None or node.data == data: return node if node.data < data: return self.search(node.right, data) else: return self.search(node.left, data) def deleteNode(self,node,data): """ Delete function will delete a node into tree. Not complete , may need some more scenarion that we can handle Now it is handling only leaf. """ # Check if tree is empty. if node is None: return None # searching key into BST. if data < node.data: node.left = self.deleteNode(node.left, data) elif data > node.data: node.right = self.deleteNode(node.right, data) else: # reach to the node that need to delete from BST. if node.left is None and node.right is None: del node if node.left == None: temp = node.right del node return temp elif node.right == None: temp = node.left del node return temp return node def traverseInorder(self, root): """ traverse function will print all the node in the tree. """ if root is not None: self.traverseInorder(root.left) print root.data self.traverseInorder(root.right) def traversePreorder(self, root): """ traverse function will print all the node in the tree. """ if root is not None: print root.data self.traversePreorder(root.left) self.traversePreorder(root.right) def traversePostorder(self, root): """ traverse function will print all the node in the tree. """ if root is not None: self.traversePreorder(root.left) self.traversePreorder(root.right) print root.data def main(): root = None tree = Tree() root = tree.insert(root, 10) print root tree.insert(root, 20) tree.insert(root, 30) tree.insert(root, 40) tree.insert(root, 70) tree.insert(root, 60) tree.insert(root, 80) print "Traverse Inorder" tree.traverseInorder(root) print "Traverse Preorder" tree.traversePreorder(root) print "Traverse Postorder" tree.traversePostorder(root) if __name__ == "__main__": main() 

Я реализовал корневое дерево как словарь {child:parent} . Так, например, с корневым узлом 0 , дерево может выглядеть так:

 tree={1:0, 2:0, 3:1, 4:2, 5:3} 

Эта структура упростила движение вверх по пути от любого узла к корню, что было актуально для проблемы, над которой я работал.

Я реализовал деревья, используя вложенные dicts. Это довольно легко сделать, и это сработало для меня с довольно большими наборами данных. Я разместил образец ниже, и вы можете увидеть больше в коде Google

  def addBallotToTree(self, tree, ballotIndex, ballot=""): """Add one ballot to the tree. The root of the tree is a dictionary that has as keys the indicies of all continuing and winning candidates. For each candidate, the value is also a dictionary, and the keys of that dictionary include "n" and "bi". tree[c]["n"] is the number of ballots that rank candidate c first. tree[c]["bi"] is a list of ballot indices where the ballots rank c first. If candidate c is a winning candidate, then that portion of the tree is expanded to indicate the breakdown of the subsequently ranked candidates. In this situation, additional keys are added to the tree[c] dictionary corresponding to subsequently ranked candidates. tree[c]["n"] is the number of ballots that rank candidate c first. tree[c]["bi"] is a list of ballot indices where the ballots rank c first. tree[c][d]["n"] is the number of ballots that rank c first and d second. tree[c][d]["bi"] is a list of the corresponding ballot indices. Where the second ranked candidates is also a winner, then the tree is expanded to the next level. Losing candidates are ignored and treated as if they do not appear on the ballots. For example, tree[c][d]["n"] is the total number of ballots where candidate c is the first non-losing candidate, c is a winner, and d is the next non-losing candidate. This will include the following ballots, where x represents a losing candidate: [cd] [xcd] [cxd] [xcxxd] During the count, the tree is dynamically updated as candidates change their status. The parameter "tree" to this method may be the root of the tree or may be a sub-tree. """ if ballot == "": # Add the complete ballot to the tree weight, ballot = self.b.getWeightedBallot(ballotIndex) else: # When ballot is not "", we are adding a truncated ballot to the tree, # because a higher-ranked candidate is a winner. weight = self.b.getWeight(ballotIndex) # Get the top choice among candidates still in the running # Note that we can't use Ballots.getTopChoiceFromWeightedBallot since # we are looking for the top choice over a truncated ballot. for c in ballot: if c in self.continuing | self.winners: break # c is the top choice so stop else: c = None # no candidates left on this ballot if c is None: # This will happen if the ballot contains only winning and losing # candidates. The ballot index will not need to be transferred # again so it can be thrown away. return # Create space if necessary. if not tree.has_key(c): tree[c] = {} tree[c]["n"] = 0 tree[c]["bi"] = [] tree[c]["n"] += weight if c in self.winners: # Because candidate is a winner, a portion of the ballot goes to # the next candidate. Pass on a truncated ballot so that the same # candidate doesn't get counted twice. i = ballot.index(c) ballot2 = ballot[i+1:] self.addBallotToTree(tree[c], ballotIndex, ballot2) else: # Candidate is in continuing so we stop here. tree[c]["bi"].append(ballotIndex) 

Ответ Грега Хьюджилла велик, но если вам нужно больше узлов на уровень, вы можете использовать список для их создания. И затем используйте метод для доступа к ним по имени или порядку (например, id)

 class node(object): def __init__(self): self.name=None self.node=[] self.otherInfo = None self.prev=None def nex(self,child): "Gets a node by number" return self.node[child] def prev(self): return self.prev def goto(self,data): "Gets the node by name" for child in range(0,len(self.node)): if(self.node[child].name==data): return self.node[child] def add(self): node1=node() self.node.append(node1) node1.prev=self return node1 

Теперь просто создайте корень и создайте его: ex:

 tree=node() #create a node tree.name="root" #name it root tree.otherInfo="blue" #or what ever tree=tree.add() #add a node to the root tree.name="node1" #name it root / child1 tree=tree.add() tree.name="grandchild1" root / child1 / grandchild1 tree=tree.prev() tree=tree.add() tree.name="gchild2" root / child1 / \ grandchild1 gchild2 tree=tree.prev() tree=tree.prev() tree=tree.add() tree=tree.name="child2" root / \ child1 child2 / \ grandchild1 gchild2 tree=tree.prev() tree=tree.goto("child1") or tree=tree.nex(0) tree.name="changed" root / \ changed child2 / \ grandchild1 gchild2 

Этого должно быть достаточно, чтобы вы начали выяснять, как сделать эту работу

Я опубликовал реализацию дерева Python [3] на моем сайте: http://www.quesucede.com/page/show/id/python_3_tree_implementation .

Надеюсь, что это полезно,

Хорошо, вот код:

 import uuid def sanitize_id(id): return id.strip().replace(" ", "") (_ADD, _DELETE, _INSERT) = range(3) (_ROOT, _DEPTH, _WIDTH) = range(3) class Node: def __init__(self, name, identifier=None, expanded=True): self.__identifier = (str(uuid.uuid1()) if identifier is None else sanitize_id(str(identifier))) self.name = name self.expanded = expanded self.__bpointer = None self.__fpointer = [] @property def identifier(self): return self.__identifier @property def bpointer(self): return self.__bpointer @bpointer.setter def bpointer(self, value): if value is not None: self.__bpointer = sanitize_id(value) @property def fpointer(self): return self.__fpointer def update_fpointer(self, identifier, mode=_ADD): if mode is _ADD: self.__fpointer.append(sanitize_id(identifier)) elif mode is _DELETE: self.__fpointer.remove(sanitize_id(identifier)) elif mode is _INSERT: self.__fpointer = [sanitize_id(identifier)] class Tree: def __init__(self): self.nodes = [] def get_index(self, position): for index, node in enumerate(self.nodes): if node.identifier == position: break return index def create_node(self, name, identifier=None, parent=None): node = Node(name, identifier) self.nodes.append(node) self.__update_fpointer(parent, node.identifier, _ADD) node.bpointer = parent return node def show(self, position, level=_ROOT): queue = self[position].fpointer if level == _ROOT: print("{0} [{1}]".format(self[position].name, self[position].identifier)) else: print("\t"*level, "{0} [{1}]".format(self[position].name, self[position].identifier)) if self[position].expanded: level += 1 for element in queue: self.show(element, level) # recursive call def expand_tree(self, position, mode=_DEPTH): # Python generator. Loosly based on an algorithm from 'Essential LISP' by # John R. Anderson, Albert T. Corbett, and Brian J. Reiser, page 239-241 yield position queue = self[position].fpointer while queue: yield queue[0] expansion = self[queue[0]].fpointer if mode is _DEPTH: queue = expansion + queue[1:] # depth-first elif mode is _WIDTH: queue = queue[1:] + expansion # width-first def is_branch(self, position): return self[position].fpointer def __update_fpointer(self, position, identifier, mode): if position is None: return else: self[position].update_fpointer(identifier, mode) def __update_bpointer(self, position, identifier): self[position].bpointer = identifier def __getitem__(self, key): return self.nodes[self.get_index(key)] def __setitem__(self, key, item): self.nodes[self.get_index(key)] = item def __len__(self): return len(self.nodes) def __contains__(self, identifier): return [node.identifier for node in self.nodes if node.identifier is identifier] if __name__ == "__main__": tree = Tree() tree.create_node("Harry", "harry") # root node tree.create_node("Jane", "jane", parent = "harry") tree.create_node("Bill", "bill", parent = "harry") tree.create_node("Joe", "joe", parent = "jane") tree.create_node("Diane", "diane", parent = "jane") tree.create_node("George", "george", parent = "diane") tree.create_node("Mary", "mary", parent = "diane") tree.create_node("Jill", "jill", parent = "george") tree.create_node("Carol", "carol", parent = "jill") tree.create_node("Grace", "grace", parent = "bill") tree.create_node("Mark", "mark", parent = "jane") print("="*80) tree.show("harry") print("="*80) for node in tree.expand_tree("harry", mode=_WIDTH): print(node) print("="*80) 
 class Tree(dict): """A tree implementation using python's autovivification feature.""" def __missing__(self, key): value = self[key] = type(self)() return value #cast a (nested) dict to a (nested) Tree class def __init__(self, data={}): for k, data in data.items(): if isinstance(data, dict): self[k] = type(self)(data) else: self[k] = data 

работает как словарь, но предоставляет столько вложенных диктонов, которые вы хотите. Попробуйте следующее:

 your_tree = Tree() your_tree['a']['1']['x'] = '@' your_tree['a']['1']['y'] = '#' your_tree['a']['2']['x'] = '$' your_tree['a']['3'] = '%' your_tree['b'] = '*' 

будет поставлять вложенный dict … который работает как дерево.

 {'a': {'1': {'x': '@', 'y': '#'}, '2': {'x': '$'}, '3': '%'}, 'b': '*'} 

… Если у вас уже есть dict, он будет кастом каждого уровня к дереву:

 d = {'foo': {'amy': {'what': 'runs'} } } tree = Tree(d) print(d['foo']['amy']['what']) # returns 'runs' d['foo']['amy']['when'] = 'now' # add new branch 

Таким образом, вы можете продолжать редактировать / добавлять / удалять каждый уровень сигнала по вашему желанию. Все методы dict для обхода и т. Д. Все еще применяются.

Какие операции вам нужны? В Python часто бывает хорошее решение, использующее dict или список с модулем bisect.

В PyPI реализовано множество реализаций деревьев, и многие типы деревьев почти тривиальны, чтобы реализовать себя в чистом Python. Однако это редко бывает необходимо.

 def iterative_bfs(graph, start): '''iterative breadth first search from start''' bfs_tree = {start: {"parents":[], "children":[], "level":0}} q = [start] while q: current = q.pop(0) for v in graph[current]: if not v in bfs_tree: bfs_tree[v]={"parents":[current], "children":[], "level": bfs_tree[current]["level"] + 1} bfs_tree[current]["children"].append(v) q.append(v) else: if bfs_tree[v]["level"] > bfs_tree[current]["level"]: bfs_tree[current]["children"].append(v) bfs_tree[v]["parents"].append(current) 
  • Проверьте требования к поддержке python 3
  • Новое для Python ... Python 3 и Matplotlib
  • Относительный импорт в Python 3 не работает
  • pandas разброс графика datetime
  • Visual Studio - NameError: имя «Tk» не определено
  • Задача Python 3.4 asyncio не выполняется полностью
  • Web Crawler Чтобы получить ссылки с нового сайта
  • Использование циклов для создания рождественской елки
  •  
    Interesting Posts for Van-Lav
    Python - лучший язык программирования в мире.