在Python中遍历树的最有效方法是什么？

Question

假设我有一个对象列表，这些对象有以下几个字段：

parent（父级）

value（值）

这些字段构成了一种树形结构，类似于文件夹树。

我想以先序遍历的方式来遍历这个列表。有没有更高效的方法呢？

通常在其他一些编程语言中，我会先找出没有父级的对象，然后对每个这样的对象，再去找出所有以它为父级的对象，依此类推。但在Python中，有没有更聪明的方法来做到这一点呢？

Answer 1

我会先创建一个更合适的数据结构，用来表示父节点和子节点之间的关系：

children = {}
for obj in tree:
    children.setdefault(obj.parent, []).append(obj)

def preorder(root, children):
    yield root.value
    for child in children.get(root, []):
        for value in preorder(child, children):
            yield value

for root in children[None]:
    for value in preorder(root, children):
        print value

你也可以在这里使用 collections.defaultdict。