高度为5的平衡二叉树最少需要多少个节点

[单选题]

高度为5的平衡二叉树最少需要多少个节点

```
10
```
```
9
```
```
11
```
```
12
```
```
其他都不对
```

查看答案及解析

adfsgkkjkj

平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。

其中F(2) = 2, F(1) = 1;

故而：F(5)= 3F(2) + 2F(1) + 4 = 12.

发表于 2019-03-30 00:43:47 回复(0)

马丘

设f（n）为高度为n的平衡二叉树最少含有的节点数，则：f(1) = 1;f(2) = 2; f(3) = 4;f(4) = 7;……

这些可以通过画图就能得到，但是当n很大时呢？其实有如下结论：f(n) = f(n-1) + f(n-2) +1,(n>=3)。这个递推结论如何得到的呢？
————————————————
版权声明：本文为CSDN博主「w57w57w57」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/w57w57w57/article/details/5921598

发表于 2020-04-12 15:45:37 回复(0)