我要招人

去企业版

首页 > 试题广场 >

若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为 1，则

[单选题]

若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为 1，则该平衡二叉树的结点总数为（）。

```
12
```
```
20
```
```
32
```
```
33
```

查看正确选项

白杨树下繁花落尽

某结点的左子树与右子树的高度(深度)差即为该结点的平衡因子（BF,Balance Factor）。

平衡二叉树上所有结点的平衡因子只可能是 -1，0 或 1。

发表于 2017-08-10 13:46:09 回复(0)

philian

除叶节点外平衡因子都为1，说明左子树都比右子树高度多1，也就是说，是左子树撑起了该局部根节点的高度，所以可以按照这样的思路，自顶而下画这棵树：（节点标号是为了区分各个节点）

为了看着清楚些，我把各层子节点提出来了，最后只需要自底而上把整个树合并起来就行。

按照fib公式算也是可以的，需要注意有的书里高度是从0开始算，有的是从1开始算。

编辑于 2016-12-16 17:11:23 回复(5)

繁星的夜空2012

最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1

或者说深度为n的平衡二叉树，至少有F(n)个结点。
Fibonacci(斐波那契)数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。注意：F(0)=0，F(1)=1。

得知平衡二叉树的最少的结点的个数为15。而对于二叉树的最多的结点的个数是i2^h-1=31.

因而用排除法，得知是20

发表于 2016-12-24 22:34:46 回复(6)

Atalia

f(n) = f(n-1)+f(n-2)+1 = F(n+2)-1 ；其中F(n) 为斐波拉契数列

发表于 2016-12-01 15:46:54 回复(0)

mrvoider

上图很清楚的说明了，就不文字再描述一遍了

其实举例举到h=4就可以证明了，举到h=5会比较清楚的看到它是个递归的结构

发表于 2021-04-10 13:40:51 回复(1)

悦千言

斐波那契数列，平衡二叉树的最小结点数：f(n)=f(n-1)+f(n-2)+1。（公式验证就不写了）

其中 f(1)=1, f(0)=0。括号中的数代表深度。

从下往上数：深度为2时，f(2)=f(1)+f(0)+1=2；

f(3)=f(2)+f(1)+1=4;

依此类推 f(4)=7,f(5)=12,f(6)=20。

发表于 2019-09-29 13:15:29 回复(0)

已注销

做个笔记，之前不知道

最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1

发表于 2017-09-10 14:24:44 回复(2)

NaNa1993

发表于 2016-11-29 16:24:19 回复(4)

AnimateDeng

1. 直接画吧，还是很快：

2. 公式算：F(n)=F(n-1)+F(n-2)+1

编辑于 2018-09-15 14:21:23 回复(1)

whoway

解法：分解问题+递推公式

我们从小问题开始，构造高为n，所有非叶结点的平衡因子均为1的图示。如下表
PS：为了简化问题，我们只画出满足条件的图示的一种即可。

图示	高度（n）	H(n)的节点个数
	1	H(1)=1
	2	H(2)=2
	3	H(3)=4

问题关键：所有非叶结点的平衡因子均为1
所以，我们可以发现，一个非叶子节点的左子树和右边子树的高度差必须是1或-1，我们以左子树高度-右子树高度=1为例。

容易发现，树的高度n>=3的时候
H(n)=根节点数+左子树节点数+右子树节点数
也就是下面的递推公式： $H(n)=1+H(n-1)+H(n-2)$

然后，知晓递推公式的通项公式：
H(1)=1;
H(2)=2;
H(n)=1+H(n-1)+H(n-2);(n>=3)
如上，如果是编程题可以写代码，还可以用“滚动数组”优化，如果是选择/填空题，就只能像下面一样

一步步递推：
H(3)=1+H(2)+H(1)=1+2+1=4;
H(4)=1+H(3)+H(2)=1+4+2=7;
H(5)=1+H(4)+H(3)=1+7+4=12;
H(6)=1+H(5)+H(4)=1+12+7=20;
选B

发表于 2020-10-17 14:52:13 回复(2)

0o0201805110004956

平衡二叉树：深度为h

最小结点数(即最小平衡二叉树的结点数)：f(h)=f(h-1)+f(h-2)+1。其中f(0)=0,f(1)=1。1表示根节点，f(h-1)表示左子树的节点数量，f(h-2)表示右子树的结点数量

最大结点数 2^h-1

发表于 2018-07-18 11:15:23 回复(0)

毛姝垚

发表于 2023-02-07 19:09:45 回复(0)

cocoonnu

是不是就是求平衡二叉树的最小节点数啊

发表于 2023-09-17 12:26:50 回复(0)

牛客938386974号

平衡因子均为1，说明任何一棵左子树都比右子树高1，也就说这棵树的深度达到了当前结点平衡二叉树最深深度，就可以套公式n(h) = n(h-1)+n(h-2)+1

发表于 2022-12-04 13:02:26 回复(0)

字节内推dd

最小二叉平衡树的节点的公式如下 :

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

得知平衡二叉树的最少的结点的个数为15。而对于二叉树的最多的结点的个数是i2^h-1=31.

因而用排除法，得知是20.

Fibonacci(斐波那契)数列：1、1、2、3、5、8、13、21、34、……

发表于 2022-03-01 13:21:21 回复(1)

Lee626

最小二叉树平衡公式 F(n)=F(n-1)+F(n-2)+1

发表于 2020-05-15 10:22:26 回复(0)

我家猫叫臭屁

做个笔记

最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1

发表于 2020-04-01 15:13:25 回复(0)

XiaoJie

我认为根据这个题目，平衡二叉查找树中，最少节点数为s(h)=s(h-1)+s(h-2)+1,s(1)=2,s(0)=1,这样计算出来，最少节点数应为33。不知为何答案选B。

发表于 2018-06-22 17:38:49 回复(1)

提交观点

问题信息

树

上传者：城市里的养猫者

难度：

18条回答 888收藏 19912浏览

若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为 1，则

解法：分解问题+递推公式

问题信息

热门推荐

相关试题