高度为h的节点数是多少？

Question

有人可以解释用于查找高度为h的节点数的方程n/(2^(h+1))吗？

[带有三节点树：

 4    h=1
2 3   h=0

对于h = 0，它是2个节点，等式给出3 /（2 ^（0 + 1））= 3/2 ^ 1 = 1.5

这是什么意思？这是如何正确的，难道方程式不应该给出高度为0的最大节点数，即2，而不是1.5？]

此等式来自算法介绍http://mitpress.mit.edu/books/introduction-algorithms

这里有关于方程式的更多信息，以及我在哪里发现的方程式：https://cs.stackexchange.com/questions/6405/maximum-number-of-nodes-with-height-hhttps://engineering.purdue.edu/~ee608/handouts/hw4s.pdf＃5

Answer 1

您误解了公式。不只是n / 2 ^{h + 1}，而是⌈n / 2 ^{h + 1}⌉（不带“英尺”是吊顶函数的表示法，它返回大于其自变量的最小整数）。

ceil(3/2^(0+1)) = ceil(3/2) 
                = ceil(1.5)
                = 2

Answer 2

在完整的二叉树中（所有级别都满的树）有ceil（n / 2）个叶子。所以树基本上就像1 2 4 8 .... Ceil(n/2).As在完整的二叉树中。number nodes at height h = 2 * number nodes at height h-1。这仅意味着要达到h级，您必须将h的叶子数除以2。因此，

number of nodes at height h in a full binary tree and maximum number of nodes at height h in complete binary tree(or almost complete binary tree) = ceil(n/2^(h+1)).