在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在这里使用.