How can I implement a tree in Python?

I am trying to construct a General tree.

Are there any built-in data structures in Python to implement it?

16 Answers

I recommend anytree (I am the author).

Example:

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 has also a powerful API with:

• simple tree creation
• simple tree modification
• pre-order tree iteration
• post-order tree iteration
• resolve relative and absolute node paths
• walking from one node to an other.
• tree rendering (see example above)
• node attach/detach hookups

Python doesn't have the quite the extensive range of "built-in" data structures as Java does. However, because Python is dynamic, a general tree is easy to create. For example, a binary tree might be:

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

You can use it like this:

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

If you need an arbitrary number of children per node, then use a list of children:

class Tree: def __init__(self, data): self.children = [] self.data = data left = Tree("left") middle = Tree("middle") right = Tree("right") root = Tree("root") root.children = [left, middle, right] 

A generic tree is a node with zero or more children, each one a proper (tree) node. It isn't the same as a binary tree, they're different data structures, although both shares some terminology.

There isn't any builtin data structure for generic trees in Python, but it's easily implemented with classes.

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

You can try:

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

As suggested here:

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.traversePostorder(root.left) self.traversePostorder(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() 

There aren't trees built in, but you can easily construct one by subclassing a Node type from List and writing the traversal methods. If you do this, I've found bisect useful.

There are also many implementations on PyPi that you can browse.

If I remember correctly, the Python standard lib doesn't include tree data structures for the same reason that the .NET base class library doesn't: locality of memory is reduced, resulting in more cache misses. On modern processors it's usually faster to just bring a large chunk of memory into the cache, and "pointer rich" data structures negate the benefit.

I implemented a rooted tree as a dictionary {child:parent}. So for instance with the root node 0, a tree might look like that:

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

This structure made it quite easy to go upward along a path from any node to the root, which was relevant for the problem I was working on.

Greg Hewgill's answer is great but if you need more nodes per level you can use a list|dictionary to create them: And then use method to access them either by name or order (like 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 

Now just create a root and build it up: 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 

That should be enough for you to start figuring out how to make this work

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 

works as a dictionary, but provides as many nested dicts you want. Try the following:

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

will deliver a nested dict ... which works as a tree indeed.

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

... If you have already a dict, it will cast each level to a tree:

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

In this way, you can keep edit/add/remove each dict level as you wish. All the dict methods for traversal etc, still apply.

If someone needs a simpler way to do it, a tree is only a recursively nested list (since set is not hashable) :

[root, [child_1, [[child_11, []], [child_12, []]], [child_2, []]]] 

Where each branch is a pair: [ object, [children] ]
and each leaf is a pair: [ object, [] ]

But if you need a class with methods, you can use anytree.

I've implemented trees using nested dicts. It is quite easy to do, and it has worked for me with pretty large data sets. I've posted a sample below, and you can see more at Google code

 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: [c d] [x c d] [c x d] [x c x x d] 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) 

I've published a Python 3 tree implementation on my site:

Here's the 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) 

If you are already using the networkx library, then you can implement a tree using that.

NetworkX is a Python package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks.

As 'tree' is another term for a (normally rooted) connected acyclic graph, and these are called 'arborescences' in NetworkX.

You may want to implement a plane tree (aka ordered tree) where each sibling has a unique rank and this is normally done via labelling the nodes.

However, graph language looks different from tree language, and the means of 'rooting' an arborescence is normally done by using a directed graph so, while there are some really cool functions and corresponding visualisations available, it would probably not be an ideal choice if you are not already using networkx.

An example of building a tree:

import networkx as nx G = nx.Graph() G.add_edge('A', 'B') G.add_edge('B', 'C') G.add_edge('B', 'D') G.add_edge('A', 'E') G.add_edge('E', 'F') 

The library enables each node to be any hashable object, and there is no constraint on the number of children each node has.

Hi you may give itertree a try (I'm the author).

The package goes in the direction of anytree package but with a bit different focus. The performance on huge trees (>100000 items) is much better and it deals with iterators to have effective filter mechanism.

>>>from itertree import * >>>root=iTree('root') >>># add some children: >>>root.append(iTree('Africa',data={'surface':30200000,'inhabitants':1257000000})) >>>root.append(iTree('Asia', data={'surface': 44600000, 'inhabitants': 4000000000})) >>>root.append(iTree('America', data={'surface': 42549000, 'inhabitants': 1009000000})) >>>root.append(iTree('Australia&Oceania', data={'surface': 8600000, 'inhabitants': 36000000})) >>>root.append(iTree('Europe', data={'surface': 10523000 , 'inhabitants': 746000000})) >>># you might use __iadd__ operator for adding too: >>>root+=iTree('Antarktika', data={'surface': 14000000, 'inhabitants': 1100}) >>># for building next level we select per index: >>>root[0]+=iTree('Ghana',data={'surface':238537,'inhabitants':30950000}) >>>root[0]+=iTree('Niger', data={'surface': 1267000, 'inhabitants': 23300000}) >>>root[1]+=iTree('China', data={'surface': 9596961, 'inhabitants': 1411780000}) >>>root[1]+=iTree('India', data={'surface': 3287263, 'inhabitants': 1380004000}) >>>root[2]+=iTree('Canada', data={'type': 'country', 'surface': 9984670, 'inhabitants': 38008005}) >>>root[2]+=iTree('Mexico', data={'surface': 1972550, 'inhabitants': 127600000 }) >>># extend multiple items: >>>root[3].extend([iTree('Australia', data={'surface': 7688287, 'inhabitants': 25700000 }), iTree('New Zealand', data={'surface': 269652, 'inhabitants': 4900000 })]) >>>root[4]+=iTree('France', data={'surface': 632733, 'inhabitants': 67400000 })) >>># select parent per TagIdx - remember in itertree you might put items with same tag multiple times: >>>root[TagIdx('Europe'0)]+=iTree('Finland', data={'surface': 338465, 'inhabitants': 5536146 }) 

The created tree can be rendered:

>>>root.render() iTree('root') └──iTree('Africa', data=iTData({'surface': 30200000, 'inhabitants': 1257000000})) └──iTree('Ghana', data=iTData({'surface': 238537, 'inhabitants': 30950000})) └──iTree('Niger', data=iTData({'surface': 1267000, 'inhabitants': 23300000})) └──iTree('Asia', data=iTData({'surface': 44600000, 'inhabitants': 4000000000})) └──iTree('China', data=iTData({'surface': 9596961, 'inhabitants': 1411780000})) └──iTree('India', data=iTData({'surface': 3287263, 'inhabitants': 1380004000})) └──iTree('America', data=iTData({'surface': 42549000, 'inhabitants': 1009000000})) └──iTree('Canada', data=iTData({'surface': 9984670, 'inhabitants': 38008005})) └──iTree('Mexico', data=iTData({'surface': 1972550, 'inhabitants': 127600000})) └──iTree('Australia&Oceania', data=iTData({'surface': 8600000, 'inhabitants': 36000000})) └──iTree('Australia', data=iTData({'surface': 7688287, 'inhabitants': 25700000})) └──iTree('New Zealand', data=iTData({'surface': 269652, 'inhabitants': 4900000})) └──iTree('Europe', data=iTData({'surface': 10523000, 'inhabitants': 746000000})) └──iTree('France', data=iTData({'surface': 632733, 'inhabitants': 67400000})) └──iTree('Finland', data=iTData({'surface': 338465, 'inhabitants': 5536146})) └──iTree('Antarktika', data=iTData({'surface': 14000000, 'inhabitants': 1100})) 

E.g. Filtering can be done like this:

>>>item_filter = Filter.iTFilterData(data_key='inhabitants', data_value=iTInterval(0, 20000000)) >>>iterator=root.iter_all(item_filter=item_filter) >>>for i in iterator: >>> print(i) iTree("'New Zealand'", data=iTData({'surface': 269652, 'inhabitants': 4900000}), subtree=[]) iTree("'Finland'", data=iTData({'surface': 338465, 'inhabitants': 5536146}), subtree=[]) iTree("'Antarktika'", data=iTData({'surface': 14000000, 'inhabitants': 1100}), subtree=[]) 

Another tree implementation loosely based off of Bruno's answer:

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 

And an example of how to use it:

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) 

Which should output:

 Root node / / \ Child node 0 Child node 1 Child node 2 | / \ Grandchild 1.0 Grandchild 2.0 Grandchild 2.1 

If you want to create a tree data structure then first you have to create the treeElement object. If you create the treeElement object, then you can decide how your tree behaves.

To do this following is the TreeElement class:

class TreeElement (object): def __init__(self): self.elementName = None self.element = [] self.previous = None self.elementScore = None self.elementParent = None self.elementPath = [] self.treeLevel = 0 def goto(self, data): for child in range(0, len(self.element)): if (self.element[child].elementName == data): return self.element[child] def add(self): single_element = TreeElement() single_element.elementName = self.elementName single_element.previous = self.elementParent single_element.elementScore = self.elementScore single_element.elementPath = self.elementPath single_element.treeLevel = self.treeLevel self.element.append(single_element) return single_element 

Now, we have to use this element to create the tree, I am using A* tree in this example.

class AStarAgent(Agent): # Initialization Function: Called one time when the game starts def registerInitialState(self, state): return; # GetAction Function: Called with every frame def getAction(self, state): # Sorting function for the queue def sortByHeuristic(each_element): if each_element.elementScore: individual_score = each_element.elementScore[0][0] + each_element.treeLevel else: individual_score = admissibleHeuristic(each_element) return individual_score # check the game is over or not if state.isWin(): print('Job is done') return Directions.STOP elif state.isLose(): print('you lost') return Directions.STOP # Create empty list for the next states astar_queue = [] astar_leaf_queue = [] astar_tree_level = 0 parent_tree_level = 0 # Create Tree from the give node element astar_tree = TreeElement() astar_tree.elementName = state astar_tree.treeLevel = astar_tree_level astar_tree = astar_tree.add() # Add first element into the queue astar_queue.append(astar_tree) # Traverse all the elements of the queue while astar_queue: # Sort the element from the queue if len(astar_queue) > 1: astar_queue.sort(key=lambda x: sortByHeuristic(x)) # Get the first node from the queue astar_child_object = astar_queue.pop(0) astar_child_state = astar_child_object.elementName # get all legal actions for the current node current_actions = astar_child_state.getLegalPacmanActions() if current_actions: # get all the successor state for these actions for action in current_actions: # Get the successor of the current node next_state = astar_child_state.generatePacmanSuccessor(action) if next_state: # evaluate the successor states using scoreEvaluation heuristic element_scored = [(admissibleHeuristic(next_state), action)] # Increase the level for the child parent_tree_level = astar_tree.goto(astar_child_state) if parent_tree_level: astar_tree_level = parent_tree_level.treeLevel + 1 else: astar_tree_level += 1 # create tree for the finding the data astar_tree.elementName = next_state astar_tree.elementParent = astar_child_state astar_tree.elementScore = element_scored astar_tree.elementPath.append(astar_child_state) astar_tree.treeLevel = astar_tree_level astar_object = astar_tree.add() # If the state exists then add that to the queue astar_queue.append(astar_object) else: # Update the value leaf into the queue astar_leaf_state = astar_tree.goto(astar_child_state) astar_leaf_queue.append(astar_leaf_state) 

You can add/remove any elements from the object, but make the structure intect.