Python树遍历问题

Question

我有一个艰难的时间与树遍历，所以避免它像瘟疫。。。正常情况下。

我有一个类是这样的：（这里有一个稍微简化的版本，但是功能上是一样的）比如：

class Branch(object):
    def __init__(self, title, parent=None):
        self.title = title
        self.parent = parent

我有一本字典，里面有很多实例，每个实例的标题都是关键字：

tree = {'Foo Branch': foo, 'Sub-Foo Branch': sub_foo, 'Bar Branch': bar}

现在，我知道有一些复杂的算法可以提高遍历效率（例如MPTT等），特别是对于效率最重要的数据库驱动项目。我根本不使用数据库，只使用简单的内存对象。

考虑到Branch的title，我需要从tree中获取该分支的所有后代的list（children，children's children，等等），因此：

1. 你还会推荐使用复杂的（对于我的无算法大脑：）算法，比如MPTT，以提高效率吗？还是有一种简单的方法可以在一个函数中实现这一点？
2. 如果是，你会推荐哪一个，知道我不使用数据库？
3. 你能举个例子吗，还是这个比我想象的要大得多？

注意：这不是家庭作业。我不在学校。我真的是算法太差了。我在一个需要数据库存储树的项目中使用了Django MPTT。。。但还是不太明白。

Answer 1

http://en.wikipedia.org/wiki/Depth-first_search

http://en.wikipedia.org/wiki/Tree_traversal

按以下步骤分两次遍历：

• 第一步：使用适当的键搜索查询节点。（如果整个树中的节点的hashmap都是all则不需要此步骤；这样（很好）就不需要执行此步骤。）

• 第二个过程：在查询节点上调用算法的修改版本，但这次，每当您访问一个节点时，都要放弃它（或者将它附加到一个非本地累加器变量）。

然而，您的情况有点奇怪，因为通常树也有指向子级的指针，有点像双链接列表。不幸的是我们没有那个信息。。。但幸运的是，添加这些信息很容易：

nodes = tree.values()
for node in nodes:
    if node.parent:
        if not hasattr(node.parent, 'children'):
            node.parent.children = []
        node.parent.children +=[ node ]

现在我们可以继续我们的例子：

def traverse(root, callback):
    """
        Peform callback on all nodes in depth-first order
        e.g. traverse(root, lambda x:print(x))
    """
    yield root, callback(root)
    for child in root.children:
        traverse(child)

def getAllDescendents(title):
    queryNode = titlesToNodes[title]  #what you call 'tree'
    for node,blah in traverse(queryNode, lambda x:None):
        yield node