问Fibonacci调用堆栈中叶子与总节点的比率

EN

叶子的数量是简单的F(n)，因为F(i)仅仅是该节点下的叶子的数量。你明白为什么了吗？(提示:使用归纳)

非叶节点的数量是叶节点的数量-1。这是二叉树的一个属性。因此，节点总数为F(n) + F(n)-1 = 2F(n)-1。

因此，当n变大时，该比率接近1/2。

fib(x)由叶fib(x-1)和叶fib(x-2)组成。所以你得到了和斐波那契数一样的递归方程。

如果终结点(叶子)是Fib1和Fib0，则

tree   numofleaves
fib2   2
fib3   3
fib4   5
fib5   8
fib6   13
...

numofleaves(x) = fib(x+1)。

对于节点的数量，您可以得到公式numnode(X)=1+numnode(x-1)+numnode(x-2)。

实际上，我通过归纳得出了一个证明，证明斐波那契树中的叶子数量总是超过内部节点的数量。

证明:设E( n )是输入n的fibonacci树的叶数，M(n)是输入n的fibonacci树的内部节点数

   E(n) >= M(n) + 1

基本情况：

f(0)：E(0) = 1，M(0) =0

f(1)：E(1) = 1，M(1) =1

f(2)：E(2) = 2，M(2) =1

f(3)：E(3) = 3，M(3) =2

大小为n的树的叶子等于每个子树的叶子：

E(n) = E(n - 1) + E(n - 2)

大小为n的树的内部节点等于每个子树的内部节点加上根

M(n) = M(n - 1) + M(n - 2) +1

E(n) >= M(n - 1) +1+ M(n - 2) + 1，(根据归纳假设)

因此，E(n) = M(n - 1) + M(n - 2) +2

因此，E(n) >= M(n) + 1，QED