Wie kann ich einen Baum in Python implementieren? Sind in Python wie in Java eingebaute Datenstrukturen vorhanden?

Ich versuche einen allgemeinen Baum zu konstruieren. Gibt es in Python eingebaute Datenstrukturen, um einen Baum zu implementieren?

anytree

Ich empfehle https://pypi.python.org/pypi/anytree

Beispiel

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')) 

Eigenschaften

Anytree hat auch eine mächtige API mit:

  • einfache Baumerstellung
  • einfache Baummodifikation
  • Baum Iteration vorbestellen
  • Post-Order-Baumiteration
  • Auflösen von relativen und absoluten Knotenpfaden
  • von einem Knoten zu einem anderen gehen.
  • Baumrendering (siehe Beispiel oben)
  • Knoten verbinden / trennen Verbindungen

Python verfügt nicht wie Java über die recht umfangreiche Palette an “eingebauten” Datenstrukturen. Da Python jedoch dynamisch ist, ist es einfach, einen allgemeinen Baum zu erstellen. Zum Beispiel könnte ein binärer Baum sein:

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

Du kannst es so benutzen:

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

Ein generischer Baum ist ein Knoten mit null oder mehr Kindern, jeder ein richtiger (Baum-) Knoten. Es ist nicht dasselbe wie ein binärer Baum, sie sind unterschiedliche Datenstrukturen, obwohl beide eine gewisse Terminologie teilen.

Es gibt keine integrierte Datenstruktur für generische Bäume in Python, aber es ist leicht mit classn zu implementieren.

 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')])]) 

Du kannst es versuchen:

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

Wie hier vorgeschlagen: https://gist.github.com/2012250

Es sind keine Bäume eingebaut, aber Sie können leicht einen erstellen, indem Sie einen Knotentyp von List ableiten und die Traversal-Methoden schreiben. Wenn Sie dies tun, habe ich herausgefunden, dass Halbierung nützlich ist.

Es gibt auch viele Implementierungen auf PyPi , die Sie durchsuchen können.

Wenn ich mich richtig erinnere, enthält die Python-Standardbibliothek keine Baumdatenstrukturen aus dem gleichen Grund wie die .NET-Basisklassenbibliothek: Speicherorte werden reduziert, was zu mehr Cache-Fehlern führt. Auf modernen processoren ist es in der Regel schneller, nur einen großen Teil des Speichers in den Cache zu bringen, und “zeigerreiche” Datenstrukturen negieren den Nutzen.

 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() 

Ich habe einen gerooteten Baum als Wörterbuch {child:parent} implementiert. So könnte zum Beispiel mit dem Wurzelknoten 0 ein Baum so aussehen:

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

Diese Struktur machte es ziemlich einfach, auf einem Pfad von irgendeinem Knoten zur Wurzel aufwärts zu gehen, was für das Problem, an dem ich arbeitete, relevant war.

Greg Hewgills Antwort ist großartig, aber wenn Sie mehr Knoten pro Level benötigen, können Sie eine Liste verwenden, um sie zu erstellen: Und dann verwenden Sie Methode, um entweder auf den Namen oder die Reihenfolge zuzugreifen (wie 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 

Jetzt erstellen Sie einfach einen Root und bauen Sie ihn auf: 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 

Das sollte genug sein, damit du beginnst, herauszufinden, wie das funktioniert

Ich habe Bäume mit verschachtelten Dicts implementiert. Es ist ziemlich einfach zu tun, und es hat für mich mit ziemlich großen Datensätzen funktioniert. Ich habe unten ein Beispiel veröffentlicht und Sie können mehr im Google-Code sehen

  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) 
 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 

funktioniert wie ein Wörterbuch, bietet aber so viele verschachtelte Diktate, wie Sie möchten. Versuche Folgendes:

 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'] = '*' 

liefert ein verschachteltes Diktat, das tatsächlich wie ein Baum funktioniert.

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

… Wenn Sie bereits ein Diktat haben, wird jede Ebene in eine Baumstruktur umgewandelt:

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

Auf diese Weise können Sie jede Diktatstufe bearbeiten / hinzufügen / entfernen, wie Sie möchten. Alle dict-Methoden für Traversal usw. gelten weiterhin.

Ich habe eine Python [3] -Baumimplementierung auf meiner Website veröffentlicht: http://www.qusucede.com/page/show/id/python_3_tree_implementation .

Hoffe es ist von Nutzen,

Ok, hier ist der Code:

 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) 

Welche Operationen benötigen Sie? In Python gibt es oft eine gute Lösung, wenn Sie ein Diktat oder eine Liste mit dem Halbierungsmodul verwenden.

Es gibt viele, viele Tree-Implementierungen auf PyPI , und viele Baumtypen sind fast trivial, um sich in reinem Python zu implementieren. Dies ist jedoch selten notwendig.

Eine andere Baum-Implementierung basiert auf Brunos Antwort :

 class Node: def __init__(self): self.name: str = '' self.children: List[Node] = [] self.parent: Node = self def __getitem__(self, i: int) -> 'Node': return self.children[i] def add_child(self): child = Node() self.children.append(child) child.parent = self return child def __str__(self) -> str: def _get_character(x, left, right) -> str: if x < left: return '/' elif x >= right: return '\\' else: return '|' if len(self.children): children_lines: Sequence[List[str]] = list(map(lambda child: str(child).split('\n'), self.children)) widths: Sequence[int] = list(map(lambda child_lines: len(child_lines[0]), children_lines)) max_height: int = max(map(len, children_lines)) total_width: int = sum(widths) + len(widths) - 1 left: int = (total_width - len(self.name) + 1) // 2 right: int = left + len(self.name) return '\n'.join(( self.name.center(total_width), ' '.join(map(lambda width, position: _get_character(position - width // 2, left, right).center(width), widths, accumulate(widths, add))), *map( lambda row: ' '.join(map( lambda child_lines: child_lines[row] if row < len(child_lines) else ' ' * len(child_lines[0]), children_lines)), range(max_height)))) else: return self.name 

Und ein Beispiel, wie man es benutzt:

 tree = Node() tree.name = 'Root node' tree.add_child() tree[0].name = 'Child node 0' tree.add_child() tree[1].name = 'Child node 1' tree.add_child() tree[2].name = 'Child node 2' tree[1].add_child() tree[1][0].name = 'Grandchild 1.0' tree[2].add_child() tree[2][0].name = 'Grandchild 2.0' tree[2].add_child() tree[2][1].name = 'Grandchild 2.1' print(tree) 

Was sollte ausgeben:

                         Wurzelknoten                        
      / / \              
 Unterknoten 0 Unterknoten 1 Unterknoten 2        
                    |  / \       
              Enkelkind 1.0 Enkelkind 2.0 Enkelkind 2.1
 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)