Python - 树遍历问题

7 投票

1 回答

12082 浏览

提问于 2025-04-16 19:00

我对树的遍历感到很困惑，所以通常会尽量避免这方面的内容……不过这次例外。

我有一个类，稍微简化一下，功能上是这样的：

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中获取这个分支的所有后代（包括子节点、孙节点等等），所以：

在我的情况下，你还会推荐使用像MPTT这样复杂的算法吗？（对于我这个没有算法基础的人来说 :)）还是有更简单的方法可以在一个函数中实现？
如果有，你会推荐哪一种，考虑到我不使用数据库？
能给个例子吗，还是说这个问题比我想的要复杂得多？

注意：这不是作业。我并不在上学。我真的对算法很糟糕。我曾经在一个需要数据库存储树的项目中使用过Django MPTT……但还是不太理解它。

数据结构内存管理递归算法子节点树遍历 mptt 后代获取

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

回答于 2025-04-16 由 Python大师

分享举报

Python - 树遍历问题

1 个回答

撰写回答