通過遞歸返回樹中所有節點的總和

我創建了霍夫曼編碼算法，該算法爲給定的一組符號及其pmf創建哈夫曼樹。我的alogrithm使用我自己的Node類，它具有實例變量string symbol,float probability,list children,string code。通過遞歸返回樹中所有節點的總和

def print_codes(root): 
    for child in root.children:        # Iterate through children 
     if (child.symbol):         # If node isn't a blank node 
      print(child.symbol + " = " + child.code)  # print its original symbol and code 
     if (child.children):        # If node has children 
      print_codes(child)        # print their codes recursively

每一父節點是一個空白節點，每個葉節點包含我編碼albhabet的標誌之一：

如下我可以通過我的樹遞歸遍歷。如果我想找到每個節點代碼長度的總和（只有節點node.symbol == True，我怎麼能在我的遞歸函數中實現這個？我將從哪個遞歸調用返回？

來源

2017-05-03 KOB

嘗試從http://stackoverflow.com/a/42147213/674064應用方法而不是「輸入1元小」的假定樹一個級別較低。 –

很難測試沒有數據，但這應該讓你更接近你的目標：

def recursive_len_sum(node): 
    temp = 0 
    if node.symbol: 
     temp += len(node.code) 
    for child in node.children: 
     temp += recursive_len_sum(child) 
    return temp 

recursive_len_sum(root)

來源

2017-05-03 14:21:32

通過遞歸返回樹中所有節點的總和

回答

相關問題