data structures – How can I implement a tree in Python?

data structures – How can I implement a tree in Python?

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 doesnt 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]

data structures – How can I implement a tree in Python?

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

There isnt any builtin data structure for generic trees in Python, but its 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)])])