如何在Python中实现树结构？

Question

我该如何在Python中实现一个通用树结构？Python里有没有现成的数据结构可以用来做这个？

Answer 1

一个通用树就是一个节点，它可以有零个或多个子节点，每个子节点也是一个完整的（树）节点。通用树和二叉树是不一样的，它们是不同的数据结构，虽然它们有一些相似的术语。

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

Answer 2

Python的内置数据结构没有Java那么多。不过，由于Python是动态的，创建一个普通的树结构非常简单。例如，一个二叉树可以是这样的：

class Tree:
    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"

如果你需要每个节点有任意数量的子节点，可以使用一个子节点的列表：

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]

Answer 3

我推荐使用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 还提供了一个强大的接口，包含：

简单的树结构创建
简单的树结构修改
前序遍历树（从根节点开始，先访问节点再访问子节点）
后序遍历树（先访问子节点再访问节点）
解析相对和绝对节点路径
在节点之间移动
树的可视化（见上面的例子）
节点的添加和移除

如何在Python中实现树结构？

20 个回答

撰写回答