遞歸提交訂單樹瀏覽

Question

我想實現如下算法：

惠譽的算法（對於一個字符序列）：

第1步：對於每一個葉節點n，打造一個集Sn包含葉的 指定的字母。

步驟2：對於每個具有子u和v的內部節點n，創建一個集合 Sn等於：•Su∩Sv，如果Su∩Sv不爲空。 •Su U Sv如果Su∩Sv是空的，則爲 。

3步驟：對於每一個內部節點n與父P，分配n.seq一個 字符等於：•p.seq如果p.seq∈的Sn的Sn•否則 的任何字符（或者如果n是根）。

我給出了一個二叉樹作爲輸入。

我已經完成了第一步，現在需要通過二叉樹遞歸地執行後序導航，以將集合分配給每個節點。我想知道如何開始這個？

使用序遞歸遍歷樹中導航作爲這樣做（這只是一個例子計算這是由多少葉子是在樹決定樹的長度葉子=沒有孩子）：

def __len__(self): 

    if self.isLeaf(): 
     print('base case - reached leaf!') 
     return 1 

    for t,w in self.children: 
     print('not leaf so sent through loop') 
     numLeaves += len(t) 

    return numLeaves 

Answer 1

它非常簡單直觀，只有在節點沒有更多的左右兒童時才標記爲已訪問節點。訪問根節點後，算法結束。如果使用遞歸進行，該算法就容易得多。

爲了讓你的算法得到適當的設置，讓你的順序遍歷返回它的賦值字符串（如果它是一個葉子，它將是一個字符）或空白字符（應該沒有孩子，無論是正確的或剩下）。

在後期訂單功能中，附加返回的字符串，然後返回附加的字符串。

http://en.wikipedia.org/wiki/Tree_traversal#Post-order