通过递归返回树中所有节点的总和

我创建了霍夫曼编码算法，该算法为给定的一组符号及其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

通过递归返回树中所有节点的总和

回答

相关问题