高度为8的平衡二叉树，至少有几个节点

高度为8的平衡二叉树，至少有几个节点

在节点最少的情况下，左右子树的高度差1，则总节点数S（n）=S（n-1）+S（n-2）+1。
初始值
S(1)  = 1
S(2)  = 2
可以推出
S(3)  = 4
S(4)  = 7
S(5)  = 12
S(6)  = 20
S(7)  = 33
S(8)  = 54
高度为8的平衡二叉树最少结点数是54


1、如果高度比较大的树，可以根据如下公式：
S（n）=S（n-1）+S（n-2）+1，此数列与斐波那契数列（F（n）=F（n-1）+F（n-2））相似，由归纳法可得S（n）=F（n+2）-1，由斐波那契定理，F（n）=（x^n）/sqrt（5），其中x=（1+sqrt（5））/2，因此可求出最少节点数。
2、假设深度为n的平衡二叉树至少有F(n)个结点,那么F(n)满足 F(n)=F(n-1)+F(n-2)+1.

引用chiconysun的回答：
设二叉树根的层次为1
如果 N(h) 是深度为 h 的平衡二叉树的最少结点数
对于 h >= 1，有 N(h) = F(h + 2) – 1 成立
其中F代表Fibonacci 序列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
因此高度为8的平衡二叉树，最少有F(8+2)-1= 55-1=4个结点设二叉树根的层次为1
如果 N(h) 是深度为 h 的平衡二叉树的最少结点数
对于 h >= 1，有 N(h) = F(h + 2) – 1 成立
其中F代表Fibonacci 序列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
因此高度为8的平衡二叉树，最少有F(8+2)-1= 55-1=54个结点

设二叉树根的层次为1
如果 N(h) 是深度为 h 的平衡二叉树的最少结点数
对于 h >= 1，有 N(h) = F(h + 2) – 1 成立
其中F代表Fibonacci 序列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
因此高度为8的平衡二叉树，最少有F(8+2)-1= 55-1=4个结点

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息