Python - 树遍历问题

Question

我在树遍历方面遇到了困难，所以像躲瘟疫一样避免它......通常情况下。

我有一个类似的类(此处稍微简化了版本，但功能相同)，例如:

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

我有一堆 Branch 实例的字典，每个实例的标题作为键:

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

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

给定 Branch 的 title，我需要获取该分支所有后代的 list( child ， child 的 child ，所以-on) 来自 tree，所以:

1. 在我的案例中，您是否仍然建议使用像 MPTT 这样复杂的(对于我没有算法的大脑:)算法来提高效率，或者是否有一种简单的方法可以在单个函数中实现这一点？
2. 如果是，您会推荐哪一个，而且我没有使用数据库？
3. 您能举个例子吗？或者这比我想象的要大得多？

注意:这不是家庭作业。我不在学校。我真的很不擅长算法。我已经将 Django MPTT 用于需要数据库存储树的项目......但仍然不太了解它。

Answer 1

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

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

你分两次遍历如下:

• 第一步:使用适当的键搜索查询节点。 (如果您有整棵树中所有节点的散列图，则不需要此步骤；您有这个(好)所以不需要此步骤。)

• 第二遍:在查询节点上调用算法的修改版本，但这一次，每当您访问一个节点时，就产生它(或将它附加到非本地累加器变量)。

  <

但是你的情况有点奇怪，因为通常树也有指向 child 的指针，有点像双链表。很遗憾，我们没有该信息……但幸运的是，添加该信息很容易:

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