python - 在 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。