tree - 当每个级别具有不同的节点数时计算树中的节点数

Question

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

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

当给出 H 并给出节点数（每个节点）时，是否有计算这些树的公式？

谢谢！

Answer 1

递归公式很明显：

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

Answer 2

如果树是完整的，那么...

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

所以一般公式是 ((((m + 1) * n + 1) ... * p + 1) * q + 1)，其中 m...q 是每个级别上的节点数。或者你可以递归地说size_n = size_{n - 1} * branchiness_n + 1。