假设我们有这种树: http ://up400.siz.co.il/up1/tymmh2wylmmo.png
当树的高度为某个 H 时,树中的每一层可以有不同数量的节点。例如,根层有3个节点(图中的“x”),下一层每个节点有2个节点(图中的“y”),下一层每个节点有4个节点(图中的“z” ), 等等...
当给出 H 并给出节点数(每个节点)时,是否有计算这些树的公式?
谢谢!
假设我们有这种树: http ://up400.siz.co.il/up1/tymmh2wylmmo.png
当树的高度为某个 H 时,树中的每一层可以有不同数量的节点。例如,根层有3个节点(图中的“x”),下一层每个节点有2个节点(图中的“y”),下一层每个节点有4个节点(图中的“z” ), 等等...
当给出 H 并给出节点数(每个节点)时,是否有计算这些树的公式?
谢谢!
递归公式很明显:
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))
如果树是完整的,那么...
所以一般公式是 ((((m + 1) * n + 1) ... * p + 1) * q + 1),其中 m...q 是每个级别上的节点数。或者你可以递归地说size_n = size_{n - 1} * branchiness_n + 1
。