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 等），特别是用于效率最重要的数据库驱动项目。我根本不使用数据库，只使用简单的内存对象。

鉴于titlea Branch，我需要从 获取list该分支的所有后代（孩子，孩子的孩子，等等）的a tree，所以：

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

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

4

1 回答 1

6

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
于 2011-06-06T04:46:19.583 回答