0

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

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

当给出 H 并给出节点数(每个节点)时,是否有计算这些树的公式?

谢谢!

4

2 回答 2

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))
于 2013-11-11T20:27:30.240 回答
0

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

  • 每个叶子下面的子树有 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

于 2013-11-11T20:25:31.670 回答