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

Question

假设我有一个对象列表，其中包含以下字段: parent

value 这定义了一种树形结构，类似于目录树。

我想以先序遍历的方式遍历该列表。最有效的方法是什么？

通常，在其他（更加命令式的）语言中，我会遍历值，找到没有父级的值，然后对于每个值，再迭代每个父级为我当前查看的父级的对象等等，但Python中是否有更聪明的方法来实现这一点？

- Bruno

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。

- Sven Marnach

---

我认为在遍历过程中不需要特别处理 obj.parent is not None，这样代码更简洁、更快，并且可以处理森林而不仅仅是树（children[None] 是所有树根的列表）。 - 6502

太好了！我想补充一下，你可以更改以下代码：def preorder(root, children,depth):yield [root.value,depth] for child in children.get(root, []): for value in preorder(child, children,depth+1): yield value这样就不仅可以看到先序遍历的结果，还可以了解每个节点的深度。请注意，第一个调用应该是 preorder(root,children,0)。非常感谢！编辑：当回复代码时，代码看起来确实很混乱。 - Bruno