什么是在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这里。