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

Question

假设我有一个包含以下字段的对象的列表

母公司

值

这定义了一个树结构，类似于目录树。在

我想以预定的方式浏览列表。最有效的方法是什么？在

通常情况下，在其他语言中，我会迭代这些值，找到没有父对象的值，然后针对每个对象再次迭代其父对象是我当前正在查看的对象，依此类推，但是在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。在