当每一层有不同数量的节点时，计算树中的节点数量

Question

假设我们有这样一棵树：http://up400.siz.co.il/up1/tymmh2wylmmo.png

当树的高度为H时，树中的每个级别可以有不同数量的节点。例如，根级别有3个节点（“图片中的x”），下一级别每个节点有2个节点（“图片中的y”），下一级别每个节点有4个节点（“图片中的z”），等等。。。

在给定H和节点数（每个节点）的情况下，有没有计算这类树的公式？

谢谢

Answer 1

如果这棵树是完整的，那么。。。

• 每个叶子下面的子树有一个节点
• 每个二级节点下的子树有1*4 1=5个节点
• 每个三级节点下的子树有5*2 1=11个节点
• 完整的树有11*3 1=34个节点

所以一般公式是（（（m1）*n1）…*p1）*q1），其中m。。。q是每个级别上的节点数。或者你可以递归地说，size_n=size_{n-1}*branchiness_n1。

Answer 2

递归公式很明显：

def node_count(level):
    n = number_of_children_for_level(level)
    if n == 0:
        return 1
    else:
        return 1 + n * node_count(level + 1)

假设级别的子节点数为3,4,2,0，则节点总数为

1 + 3 * (1 + 4 * (1 + 2 * 1))