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

Question

我已经为霍夫曼编码创建了一个算法，该算法为给定的一组符号及其 pmf 创建霍夫曼树。我的算法使用我自己的 Node class，它具有实例变量 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 的节点，我怎么能在我的递归函数中实现这个？我从哪里 return 从每个递归调用？

Answer 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)

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

Returning the sum of all nodes in a tree through recursion

python

recursion

huffman-code