我在树遍历方面遇到了困难,所以像躲瘟疫一样避免它......通常情况下。
我有一个类似的类(此处稍微简化了版本,但功能相同),例如:
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
,所以:
- 在我的案例中,您是否仍然建议使用像 MPTT 这样复杂的(对于我没有算法的大脑:)算法来提高效率,或者是否有一种简单的方法可以在单个函数中实现这一点?
- 如果是,您会推荐哪一个,而且我没有使用数据库?
- 您能举个例子吗?或者这比我想象的要大得多?
注意:这不是家庭作业。我不在学校。我真的很不擅长算法。我已经将 Django MPTT 用于需要数据库存储树的项目......但仍然不太了解它。
最佳答案
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
关于Python - 树遍历问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6247751/