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等），特別是與數據庫驅動的項目中使用，其中效率事項複雜的算法大多數。我根本不使用數據庫，只使用簡單的內存中對象。

鑑於一個Branch的title，我需要從tree該分支的所有後代（孩子，孩子的孩子，所以-ON）的list，所以：

1. 你仍然使用的是推薦複雜（對於我的算法大腦:)像MPTT算法效率在我的情況下，還是有一種簡單的方法來實現這一點在一個單一的功能？
2. 如果是這樣，你會推薦哪一個，知道我沒有使用數據庫？
3. 你能提供一個例子，還是比我想象的要大得多？

注意：這不是一項家庭作業。我不在學校。算法上我真的很不好。我使用Django MPTT開發了一個需要數據庫存儲樹的項目......但仍然不太瞭解它。

Answer 1

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

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

你穿越在兩道如下：

• 第一遍：搜索與相應的鍵查詢節點。 （這一步是不必要的，如果你有所有在整個樹中的節點一個HashMap，你有這個（好），所以這一步是沒有必要的。）

• 第二遍：調用算法的修改版本在查詢節點上，但是這次，每當你訪問一個節點時，產生它（或者將它附加到一個非本地累加器變量）。

然而，你的情況有點奇怪，因爲通常樹還有指向兒童的指針，有點像雙鏈表。不幸的是我們沒有這方面的資料......幸好它很容易添加信息：

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