Question

具有5层结点的平衡二叉树至少有多少个结点

Answer 1

至少有12个结点。

分析过程如下：

因为根结点层次为1，则高度为h的平衡二叉树最少有F(h + 2) -1个结点；

其中F 为Fibonacci序列1, 1, 2, 3, 5, 8, 13, 21,...；

Fibonacci数列种，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子数的节点数量；

易知F(1)=1，F(2)=2，F(3)=4 ；

F(5)=F(4)+F(3)+1=2*F(3)+F(2)+2；

因为F(2)=2，F(3)=4；

故F(5)=2*F(3)+F(2)+2=2*4+2+2=12；

即具有5层结点的平衡二叉树至少有12个结点。

此题利用了平衡二叉树的性质解题。

扩展资料：

平衡二叉树的性质：

1、它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树；

2、常用算法有红黑树、AVL、Treap、伸展树等。在平衡二叉搜索树中，其高度一般都良好地维持在O（log（n）），大大降低了操作的时间复杂度；

3、若根结点层次为1，则高度为h的平衡二叉树最少有F(h + 2) -1个结点，其中F 为Fibonacci序列1, 1, 2, 3, 5, 8, 13, 21,...；

4、最小二叉平衡树的节点总数的公式如下 F(n)=F(n-1)+F(n-2)+1，可以参考Fibonacci(斐波那契)数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。

参考资料来源：百度百科—平衡二叉树

Answer 2

2^(5-2)-1+2^(5-4)+3=12（个）
答：具有5层结点的平衡二叉树至少有12个结点。

平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。构造与调整方法 平衡二叉树的常用算法有红黑树、AVL、Treap等。 最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。

Answer 3

如果根的层次为1，则5层结点的平衡二叉树至少有F(h +2)-1个结点
F为Fibonacci序列1, 1, 2, 3, 5, 8, 13, 21, 34,...
因此F(5 + 2) - 1 = 13 - 1 = 12个结点

Answer 4

2^(5-2)-1+2^(5-4)+3=12（个）
答：具有5层结点的平衡二叉树至少有12个结点。

平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。构造与调整方法 平衡二叉树的常用算法有红黑树、AVL、Treap等。 最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。

Answer 5

有12个节点

如果根结点层次为1，则高度为h的平衡二叉树最少有F(h + 2) -1个结点
其中F 为Fibonacci序列1, 1, 2, 3, 5, 8, 13, 21,...
因此5层最少有F(7) -1 = 13-1 = 12个结点

http://baike.baidu.com/albums/593144/593144.html#0$dbf554ed49e91f9cb21cb140
就像上面这张图，平衡二叉树的定义是其中任意结点两个子树高度之差的绝对值不超过1
你可以试试看能不能把上面这颗树减少一个结点而不违反性质的