二叉树

树形结构中二叉树的内容考察最多，所以重点要复习二叉树。

二叉树的概念

• 根节点（root node）：位于二叉树顶层的节点，没有父节点。

• 叶节点（leaf node）：没有子节点的节点，其两个指针均指向 None 。

• 边（edge）：连接两个节点的线段，即节点引用（指针）。

• 节点所在的层（level）：从顶至底递增，根节点所在层为 1 。

• 节点的度（degree）：节点的子节点的数量。在二叉树中，度的取值范围是 0、1、2 。

• 二叉树的高度（height）：从根节点到最远叶节点所经过的边的数量。

• 节点的深度（depth）：从根节点到该节点所经过的边的数量。

• 节点的高度（height）：从距离该节点最远的叶节点到该节点所经过的边的数量。

一、二叉树的性质

• 性质1：二叉树第 $i$ 层上的结点数目最多为 $2^{i-1}(i \ge 1)$。
• 性质2： $k$ 层的二叉树至多有 $2^0+2^1+ \dots +2^{k-1} = 2^k-1$ 个结点。
• 性质3：二叉树中，叶子节点数为 $n_0$，度为 $2$ 的结点数为 $n_2$ ，则有： $n_0=n_2+1$。

二、满二叉树和完全二叉树

• 1、满二叉树 ：一棵层数为 $k$ 且有 $2^k-1$ 个结点的二又树称为满二叉树。

  • 特点： 每层都有 $2^{i-1}$ 个点（饱满）。

• 2、完全二叉树：除了最下层，其他每层都饱满，最下层的结点都集中在该层最左边的若干位置上。

  • 特点：

    • ①、满二叉树是完全二叉树，完全二叉树不一定是满二叉树；

    • ②、在满二叉树的最下层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。

    • ③、在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。

    • ④、若 $i$ 为结点编号，则若 $i \ne 1$ ，则其父结点的编号为 $\lfloor \frac i 2 \rfloor$ ；若 $2i \le N$，则其左儿子（即左子树的根结点）的编号为 $2i$；若 $2i > N$，则无左儿子。若 $2i+1 \le N$ ，则其右儿子的结点编号为 $2i+1$ ；若 $2i+1 > N$ ，则无右儿子。

例题1：已知完全二叉树的点数，求完全二叉树的层数。

具有3个结点的完全二叉树的层数为（ 2 ）

具有6个结点的完全二叉树的层数为（ 3 ）

具有8个结点的完全二叉树的层数为（ 4 ）

具有125个结点的完全二叉树的层数为（ 7 ）

具有1024个结点的完全二叉树的层数为（ 11 ）

解：

设所求完全二叉树的层数为 $k$。

层数为 $k$ 的完全二叉树的前 $k-1$ 层为层数为 $k-1$ 的满二叉树，一共有 $2^(k-1)-1$ 个结点。

由于完全二叉树深度为 $k$ ，故第 $k$ 层上还有若干个结点，因此： $2^{k-1}-1 < n \le 2^k -1$。

可推出： $2^{k-1} \le n < 2^k$

可推出： $k-1 \le \log_2n < k$

可推出： $k= \lfloor \log_2n \rfloor +1$

练习

1. [CSP 2024 提高级第一轮 第 11 题] 假设有一棵 h 层的完全二叉树，该树最多包含多少个结点？（ A ）{{ select(1) }}

• $2^h−1$
• $2 ^{h+1}−1$
• $2^h$
• $2^{h+1}$

2. 完全二叉树的顺序存储方案，是指将完全二叉树的结点从上至下、从左至右依次存放到一个顺序结构的数组中。假定根结点存放在数组的 $1$ 号位置，则第 $k$ 号结点的父结点如果存在的话，应当存放在数组的（ C ）号位置。{{ select(2) }}

• $2k$
• $2k+1$
• $\lfloor \frac k 2 \rfloor$
• $\lfloor \frac {k+1} 2 \rfloor$

3. 如果根结点的深度记为1，则一棵恰有2011个叶结点的二叉树的深度最少是（ C ）。{{ select(3) }}

• 10
• 11
• 12
• 13

4. 已知一棵二叉树有10 个节点，则其中至多有（ A ）个节点有 2 个子节点。{{ select(4) }}

• 4
• 5
• 6
• 7

5. 如果根的高度为 1,具有 61 个结点的完全二叉树的高度为( B )。{{ select(5) }}

• 5
• 6
• 7
• 8

6. 一棵结点数为 2015 的二叉树最多有（ B ）个叶子结点。{{ select(6) }}

• 1007
• 1008
• 2014
• 2015

7. 一棵二叉树如右图所示，若采用顺序存储结构，即用一 维数组元素存储该二叉树中的结点（根结点的下标为 1， 若某结点的下标为 i，则其左孩子位于下标2i处、 右孩子位于下标(2i+1)处） ，则图中所有结点的最大下标为( D ) 。 {{ select(7) }}

• 6
• 10
• 12
• 15

8. 约定二叉树的根节点高度为 1。一棵结点数为 2016 的二叉树最少有（）个叶子结点；一棵结点数为 2016 的二叉树最小的高度值是（ A ）。{{ select(8) }}

• 1 11
• 2 10
• 2 12
• 1 12

9. 根节点深度为 0，一棵深度为 h 的满 k（k>1）叉树，即除最后一层无任何子节点外，每一层上的所有结点都有k 个子结点的树，共有( A )个结点。{{ select(9) }}

• $\frac {k^{h+1}−1} {k−1}$
• $k^{h−1}$
• $k^h$
• $\frac {k^{h−1}} {k−1}$

10. 一棵二叉树如右图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为1,若某结点的下标为i ,则其左孩子位于下标2i处、右孩子位于下标2i+1处），则该数组的最大下标至少为( C )。 {{ select(10) }}

• 6
• 10
• 15
• 12

11. 独根树的高度为 1,具有 61 个结点的完全二叉树的高度为( B )。{{ select(11) }}

• 5
• 6
• 7
• 8

12. 如果一棵二叉树只有根结点，那么这棵二叉树高度为1。请问高度为5的完全二叉树有（ A ）种不同形态?{{ select(12) }}

• 16
• 15
• 17
• 32

13. 一棵有 n 个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第 1 个位置。若存储在数组第 9 个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是（ C ）。{{ select(13) }}

• 8 、18
• 10、 18
• 8、 19
• 10、19

14. 根节点的高度为1，一 棵拥有2023个节点的三叉树高度至少为（ C ）。{{ select(14) }}

• 6
• 7
• 8
• 9

15. 假设有一组字符 {a,b,c,d,e,f}, 对应的频率分别为5%、9%、12%、13%、16%、45%。请问以下哪个选项是字符 a,b,c,d,e,f 分别对应的一组哈夫曼编码 （ A ）?{{ select(15) }}

• 1111,1110,101,100,110,0
• 1010,1001,1000,011,010,00
• 000,001,010,011,10,11
• 1010,1011,110,111,00,01

16. 一棵具有5层的满二叉树中结点数为( A )。{{ select(16) }}

• 31
• 32
• 33
• 16