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等),尤其适用于效率最重要的数据库驱动项目.我根本不使用数据库,只使用简单的内存中对象.

考虑到titlea Branch,我需要得到list该分支的所有后代(儿童,孩子的孩子,等等)tree,所以:

1. 你是否仍然建议在我的情况下使用像MPTT这样的复杂(对于我的算法)算法来提高效率,或者是否有一种简单的方法可以在单个函数中实现这一点？
2. 如果是这样,你会推荐哪一个,知道我没有使用数据库？
3. 你能提供一个例子,还是比我想的要大得多？

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

Answer 1

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

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

你在两遍中遍历如下:

• 第一遍:使用适当的密钥搜索查询节点.(如果您有整个树中所有节点的散列图,则此步骤是不必要的;您有此(好)所以此步骤不是必需的.)

• 第二遍:在查询节点上调用算法的修改版本,但这次,每当您访问节点时,将其生成(或将其附加到非本地累加器变量).

但是你的情况有点奇怪,因为通常树也有指向孩子的指针,有点像双链表.不幸的是我们没有这些信息......但幸运的是,添加这些信息很容易:

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