Python - 树遍历问题

Question

Python - 树遍历问题

pythonalgorithmbinary-treetree-traversal

7

我在树的遍历方面遇到了困难，所以通常会像瘟疫一样避免它...

我有一个类，有点像这个简化版本（但功能上相同）：

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”，我需要从“tree”中获取该分支的所有后代（子代、子孙等）的列表，因此：

1. 在我的情况下，您仍然建议使用像MPTT这样复杂的算法以实现效率，还是有一种简单的方式可以通过单个函数实现？

2. 如果是这样，请问您会建议哪种算法，知道我不使用数据库？

3. 您能提供一个示例吗，还是它比我想象的要大得多？

注意：这不是作业任务。我不在学校里。我只是在算法方面很差。我曾经为一个需要存储在数据库中的树形结构项目使用了Django MPTT……但仍然不太理解它。

- orokusaki

如果我必须猜测的话，我会说答案在递归中。 - orokusaki

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ninjagecko · Accepted Answer

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