How can I implement a tree in Python?

I recommend anytree (I am the author).

Example:

from anytree import Node, RenderTreeudo = 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    └── Joeprint(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 = dataleft = 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   4t = Tree('*', [Tree('1'),               Tree('2'),               Tree('+', [Tree('3'),                          Tree('4')])])