外观
4.6 二叉树的性质
第i层最多几个结点
4.5节那棵二叉树,高度是3,有5个结点。图里还有两个虚线框空着。
本节问题高度不变,这棵树里最多还能放几个结点?
要回答它,先一层一层看,每层最多能放几个。二叉树的每个结点最多两个孩子,所以下一层最多是这一层的两倍:
第1层:1个。第1层只有根。
第2层:2个。根最多两个孩子。
第3层:4个。第2层的B、C,各自最多两个孩子,2 × 2 = 4。
每往下一层,最多的个数翻一倍:1、2、4、8……第i层是i − 1个2相乘,写作2ⁱ⁻¹。
这是二叉树的第一个性质:第i层最多有2ⁱ⁻¹个结点。第3层最多2²,也就是4个。
总共最多几个结点
一层一层加起来,就是整棵树最多的个数:
高度1:最多1个。只有第1层。
高度2:最多3个。1 + 2 = 3。
高度3:最多7个。1 + 2 + 4 = 7。
总数1、3、7,每个都加1看看:2、4、8,正好每次翻一倍。因为每加一层,新一层的个数正好等于原来的总数加1:第2层2个,是1加1;第3层4个,是3加1。
所以高度为h时,总数加1是2ʰ,总数是2ʰ − 1。
这是二叉树的第二个性质:高度为h的二叉树,最多有2ʰ − 1个结点。
回到本节问题。高度为3,最多2³ − 1 = 7个结点。现在有5个,还能放2个,正好是那两个虚线框。
满二叉树
把两个虚线框都放上结点:B的右孩子E,C的左孩子F。这棵树有7个结点,达到了高度3能放的最多个数。
高度为h、有2ʰ − 1个结点的二叉树,叫满二叉树。
每一层都排满。第1层1个,第2层2个,第3层4个,每一层都达到了最多。
叶子都在最下一层。D、E、F、G都在第3层,上面两层没有叶子。
其余结点都有两个孩子。A、B、C的度都是2,没有度为1的结点。
满二叉树每个位置都有结点,可以给它们编号。从根开始,从上到下,每层从左到右,依次是1到7:
编号就是位置。B在2号位置,它的左孩子D在4号,右孩子E在5号。
完全二叉树
结点数不够排满时,就从最大的编号往前空。
高度为h、有n个结点的二叉树,每个结点都和高度为h的满二叉树里编号1到n的结点一一对应,叫完全二叉树。
6个结点:去掉7号。剩下的A到F,正好占着1号到6号。是完全二叉树。
5个结点:再去掉6号。A到E占着1号到5号。还是完全二叉树。
4.5节那棵:不是。它也有5个结点,可是G占着7号,5号、6号空着。编号对不上1到5。
满二叉树也是完全二叉树。7个结点占着1号到7号,一个不空。
编号连成一片、中间不空,还能看出两点:
叶子只在最下面两层。5个结点那棵,叶子是第2层的C,和第3层的D、E。
度为1的结点最多一个,而且只有左孩子。6个结点那棵,只有C的度是1,它的孩子F在左下。
程序为什么在乎:编号中间不空,按编号把结点放进数组,一格也不浪费。讲二叉树的存储时,会用到这些编号。
叶子比度为2的结点多一个
最后一个性质,讲的是度,和最多几个结点无关。
把二叉树的结点按度分成三类。叶子的度是0,有n₀个;度为1的有n₁个;度为2的有n₂个。
4.1节验算过:所有结点的度加起来,等于结点数减1。因为除了根,每个结点都是某个结点的孩子,在度里恰好被数了一次。
- 结点数是n₀ + n₁ + n₂;
- 度加起来是n₁ + 2n₂:度为1的每个算1,度为2的每个算2,叶子不算。
所以n₁ + 2n₂ = n₀ + n₁ + n₂ − 1。两边都减去n₁和n₂,得到:
text
n₀ = n₂ + 1这是二叉树的第三个性质:叶子比度为2的结点多一个。用这一节的三棵树验算:
4.5节那棵。叶子是D、G,2个。度为2的只有A,1个。2 = 1 + 1。
满二叉树。叶子是D、E、F、G,4个。度为2的是A、B、C,3个。4 = 3 + 1。
6个结点的完全二叉树。叶子是D、E、F,3个。度为2的是A、B,2个。3 = 2 + 1。
度为1的结点,三棵树里分别有2个、0个、1个,都不影响结果。n₁在等式两边各出现一次,抵消了。
例题:8个人的淘汰赛
题目8个人打单场淘汰赛:每场两人,输的出局,赢的进下一轮,直到决出冠军。把每个人、每场比赛都当作结点,一场比赛的两个孩子是打这场的两方。一共要比几场?对阵表画成二叉树,有几层、几个结点?
分析。
- 叶子比度为2的结点多一个:8个人是叶子,n₀ = 8。每场比赛都有两方,是度为2的结点。所以比赛有n₂ = 8 − 1 = 7场。
- 第i层最多有2ⁱ⁻¹个结点:8个人都在最下一层。2³ = 8,最下一层至少是第4层;对阵表正好是4层。
- 高度为h的二叉树,最多有2ʰ − 1个结点:8个人加7场比赛,一共15个结点。高度4最多2⁴ − 1 = 15个,一个不少,所以是满二叉树。
答案要比7场。对阵表是4层、15个结点的满二叉树。
练习1:高度为4的二叉树
填空
一棵高度为4的二叉树:
- 第3层最多有 个结点
- 第4层最多有 个结点
- 整棵树最多有 个结点
第i层最多2ⁱ⁻¹个:第3层2² = 4,第4层2³ = 8。整棵最多2⁴ − 1 = 15,也就是1 + 2 + 4 + 8。16是忘了减1;7是高度3的答案。
练习2:哪些是完全二叉树?
多选
按编号的办法,判断下面哪几棵是完全二叉树。
A
①
4个结点,占着1号到4号。
B
②
E在B的右下,是5号;4号空着。
C
③
F在C的左下,是6号;4号、5号空着。
D
④
满二叉树,1号到7号都有结点。
判断的办法:按满二叉树的位置编号,看结点是不是正好占着1号到n号。
练习3:叶子有几个?
填空
用叶子比度为2的结点多一个,算一算:
- 一棵二叉树有5个度为2的结点、3个度为1的结点。它有 个叶子,一共 个结点
- 5个人打单场淘汰赛,一共要比 场
叶子n₀ = n₂ + 1 = 6,结点数6 + 3 + 5 = 14。淘汰赛里5个人是叶子,比赛是度为2的结点,5 = n₂ + 1,所以比4场。
到这里你有了二叉树的三个性质:第i层最多2ⁱ⁻¹个结点;高度为h最多2ʰ − 1个结点;叶子比度为2的结点多一个,n₀ = n₂ + 1。两种特殊的二叉树:满二叉树,每一层都排满;完全二叉树,结点和满二叉树的1号到n号一一对应。下一步完全二叉树的编号连成一片。按编号把结点放进数组,就是二叉树的顺序存储。