408

数据结构

DS-04-01 二叉树的定义与性质

---

一、定位信息

项目	内容
圈层	核心层（大纲考点）
前置知识	树的基本概念（节点、度、层、深度）、递归思想
知识网络定位	本单元是第四章"树和二叉树"的理论基础，为后续遍历、线索化、哈夫曼编码等提供性质支撑
考点热度	H级（高频重点）：二叉树性质几乎每年选择题必考，近5年累计出现≥5次

---

二、知识点讲解

2.1 二叉树的定义

二叉树（Binary Tree） 是一种树形结构，其特点是每个节点至多有两棵子树，且子树有左右之分，次序不可颠倒。

递归定义：二叉树是 $n$（$n \geq 0$）个节点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

关键理解：

• 二叉树的子树有左右之分，这是它与度为2的有序树的本质区别
• 度为2的有序树至少有3个节点（根+两个孩子），而二叉树可以为空
• 二叉树中某个节点即使只有一个孩子，也必须区分是左孩子还是右孩子

示例：设根节点为A，A的左子节点为B，右子节点为C。B的左子节点为D，右子节点为空。C的左子节点为空，右子节点为E。则该二叉树有5个节点，A的度为2，B的度为1，C的度为1，D和E的度为0。

2.2 两种特殊的二叉树

满二叉树（Full Binary Tree）：一棵深度为 $k$ 且有 $2^k - 1$ 个节点的二叉树。每层的节点数都达到最大值，所有分支节点的度都为2，叶子节点都在最底层。

完全二叉树（Complete Binary Tree）：深度为 $k$、有 $n$ 个节点的二叉树，当且仅当其每个节点都与深度为 $k$ 的满二叉树中编号从 $1$ 到 $n$ 的节点一一对应时，称为完全二叉树。

完全二叉树的等价判定条件：

1. 叶子节点只可能出现在最后两层
2. 若存在度为1的节点，则最多只有1个，且该节点只有左孩子
3. 按层序编号后，对于任意节点 $i$：若 $2i \leq n$，则 $i$ 有左孩子（编号为 $2i$）；若 $2i+1 \leq n$，则 $i$ 有右孩子（编号为 $2i+1$）

2.3 二叉树的五大性质（必须掌握）

性质1：在二叉树的第 $i$ 层上至多有 $2^{i-1}$ 个节点（$i \geq 1$）。

证明：用数学归纳法。当 $i=1$ 时，只有根节点，$2^{1-1}=1$，成立。假设第 $k$ 层至多 $2^{k-1}$ 个节点，由于每个节点至多有2个子节点，第 $k+1$ 层至多有 $2 \times 2^{k-1} = 2^k$ 个节点。由归纳法，性质成立。$\blacksquare$

性质2：深度为 $k$ 的二叉树至多有 $2^k - 1$ 个节点（$k \geq 1$）。

证明：由性质1，深度为 $k$ 的二叉树最多有 $\sum_{i=1}^{k} 2^{i-1} = 2^k - 1$ 个节点（等比数列求和）。$\blacksquare$

性质3：对任何二叉树 $T$，若叶子节点数为 $n_0$，度为2的节点数为 $n_2$，则 $n_0 = n_2 + 1$。

证明：设节点总数为 $n$，度为1的节点数为 $n_1$，则 $n = n_0 + n_1 + n_2$。从边的角度看，除根节点外每个节点恰好对应一条入边，总边数为 $n - 1$。度为1的节点贡献1条边，度为2的节点贡献2条边，所以总边数也等于 $n_1 + 2n_2$。联立：$n - 1 = n_1 + 2n_2$，代入 $n = n_0 + n_1 + n_2$，得 $n_0 + n_1 + n_2 - 1 = n_1 + 2n_2$，化简得 $n_0 = n_2 + 1$。$\blacksquare$

性质4：具有 $n$ 个节点的完全二叉树的深度为 $\lfloor \log_2 n \rfloor + 1$。

证明：设深度为 $k$，由完全二叉树定义，$2^{k-1} - 1 < n \leq 2^k - 1$，即 $2^{k-1} \leq n < 2^k$（左边界由 $n$ 为正整数保证）。取对数得 $k-1 \leq \log_2 n < k$，所以 $k = \lfloor \log_2 n \rfloor + 1$。$\blacksquare$

性质5：对有 $n$ 个节点的完全二叉树按层序编号（根为1），对于任意节点 $i$：

• 若 $i=1$，则节点 $i$ 是根节点，无双亲
• 若 $i > 1$，则双亲节点编号为 $\lfloor i/2 \rfloor$
• 若 $2i \leq n$，则左孩子编号为 $2i$；否则无左孩子
• 若 $2i+1 \leq n$，则右孩子编号为 $2i+1$；否则无右孩子

证明：完全二叉树按层序编号后，第 $k$ 层的第一个节点编号为 $2^{k-1}$，最后一个为 $2^k - 1$。对于编号为 $i$ 的节点，它在第 $\lfloor \log_2 i \rfloor + 1$ 层。它的左孩子编号为 $2i$（如果存在），右孩子编号为 $2i+1$（如果存在），双亲编号为 $\lfloor i/2 \rfloor$（如果存在）。这可以通过完全二叉树的层序编号规则直接验证。$\blacksquare$

---

三、记忆与理解辅助

技巧1：二叉树五大性质速记口诀

"层倍树减一，叶等二加一，深度取对数，编号父子系"

• 层倍：第 $i$ 层最多 $2^{i-1}$ 个
• 树减一：深度 $k$ 最多 $2^k-1$ 个
• 叶等二加一：$n_0 = n_2 + 1$
• 深度取对数：$k = \lfloor \log_2 n \rfloor + 1$
• 编号父子系：父 $\lfloor i/2 \rfloor$，左 $2i$，右 $2i+1$

技巧2：三种二叉树对比表

特征	普通二叉树	满二叉树	完全二叉树
定义	每个节点至多2个子树	每层节点数都达到最大	节点按层序连续编号无间断
节点数	$0 \leq n \leq 2^k-1$	恰好 $2^k-1$	$2^{k-1} \leq n \leq 2^k-1$
叶子位置	任意层	仅在最后一层	只在最后两层
度为1的节点	任意多个	0个	最多1个（且只有左孩子）
层序编号	不一定连续	必然连续	必然连续
包含关系	最一般	是特殊的完全二叉树	满二叉树是其特例

技巧3：性质3的"握手定理"类比

性质3 $n_0 = n_2 + 1$ 类似图论中的握手定理：每个度为2的节点"产生"2条出边，度为1的节点产生1条出边，叶子节点产生0条。总出边 = 总节点数 - 1（根无入边）。由此可推导出 $n_0 = n_2 + 1$，与 $n_1$ 无关。记住：这个公式不涉及度为1的节点数。

技巧4：完全二叉树编号快速判断法

对完全二叉树按层序编号从1开始：

• 找父：$i/2$ 取整（如节点7的父是 $\lfloor 7/2 \rfloor = 3$）
• 找左子：$2i$（如节点3的左子是6）
• 找右子：$2i+1$（如节点3的右子是7）
• 判断是否有孩子：$2i > n$ 则无孩子（叶子节点）

---

四、例题与精解

例题1（基础巩固）

题目：一棵完全二叉树有100个节点，求叶子节点数、度为1的节点数和度为2的节点数。

命题意图：考查完全二叉树的性质综合运用，特别是性质3和完全二叉树的结构特征。

审题分析：已知 $n=100$，完全二叉树。需要求 $n_0$、$n_1$、$n_2$。

解题思路：

1. 利用完全二叉树特征确定 $n_1$
2. 利用性质3求 $n_0$
3. 利用总节点数求 $n_2$

完整步骤：

Step 1：由性质4，深度 $k = \lfloor \log_2 100 \rfloor + 1 = \lfloor 6.64 \rfloor + 1 = 7$。

Step 2：完全二叉树中，度为1的节点只可能出现在倒数第二层的最右侧。前6层共有 $2^6 - 1 = 63$ 个节点，第7层有 $100 - 63 = 37$ 个叶子节点。

Step 3：第6层最后一个节点编号为63，它的左孩子编号为126 > 100，所以第6层的某些节点可能没有孩子。第6层有 $2^5 = 32$ 个节点。第7层37个叶子节点需要 $\lceil 37/2 \rceil = 19$ 个父节点（在第6层）。所以第6层有 $32 - 19 = 13$ 个叶子节点。

更简洁的方法：

• 完全二叉树中 $n_1$ 要么为0要么为1
• $n = 100$ 为偶数，说明存在编号为50的节点，它是节点25的左孩子
• 节点50是最后一个节点，是左孩子，所以存在度为1的节点（节点25），$n_1 = 1$
• 由 $n = n_0 + n_1 + n_2 = 100$ 和 $n_0 = n_2 + 1$：
  • $n_2 + 1 + 1 + n_2 = 100$
  • $2n_2 = 98$，$n_2 = 49$
  • $n_0 = 50$

答案：叶子节点50个，度为1的节点1个，度为2的节点49个。

方法反思：完全二叉树中 $n_1$ 的判断技巧：$n$ 为奇数时 $n_1 = 0$，$n$ 为偶数时 $n_1 = 1$。这是因为完全二叉树的最后一个节点如果是右孩子（$n$ 为奇数，最后一个编号为奇数），则不存在度为1的节点。

例题2（中等提升）

题目：已知一棵二叉树的先序序列为 ABCDEFG，中序序列为 CBDAEGF，请画出该二叉树并求叶子节点数。

命题意图：考查由遍历序列还原二叉树结构的能力，以及性质3的应用。

审题分析：已知先序（根左右）和中序（左根右），需要还原二叉树。

解题思路：先序的第一个元素是根，在中序中找到根的位置可划分左右子树，递归处理。

完整步骤：

Step 1：先序首元素 A 是根。在中序 CBDAEGF 中，A 的左边 CBD 是左子树，右边 EGF 是右子树。

Step 2：左子树的先序为 BCD，中序为 CBD。先序首元素 B 是根，在中序中 B 左边是 C（左子树），右边是 D（右子树）。

Step 3：右子树的先序为 EFGF，中序为 EGF。先序首元素 E 是根，在中序中 E 左边为空（无左子树），右边 GF 是右子树。

Step 4：GF 的先序为 FG，中序为 GF。F 是根，G 是左子树。

Step 5：最终二叉树结构：

• 根：A
• A 的左子：B，A 的右子：E
• B 的左子：C，B 的右子：D
• E 的左子：无，E 的右子：F
• F 的左子：G，F 的右子：无

Step 6：叶子节点为 C、D、G，共 3 个。验证：$n=7$，$n_2=2$（A、B），$n_1=2$（E、F），$n_0 = n_2 + 1 = 3$。✓

答案：叶子节点数为3。

方法反思：先序+中序或后序+中序可唯一确定二叉树，但先序+后序不能（除非是满二叉树）。还原时的关键是"在中序中找到根的位置来划分左右子树"。

---

五、考情分析

项目	内容
考查频次	近5年选择题几乎每年必考，平均1-2题
常见题型	选择题（给定节点数求叶子数、判断完全二叉树）、填空题（由遍历序列求节点数）
分值占比	选择题2-4分，偶尔在综合题中作为小问出现
命题趋势	性质3（$n_0 = n_2 + 1$）是核心考点，常与完全二叉树性质4、5结合考查。近年倾向于将性质与遍历序列结合出综合题
考查方式	给定完全二叉树节点数求各度节点数；给定遍历序列还原树后求性质；判断某棵二叉树是否为完全二叉树

基于大纲与命题规律推测：二叉树性质属于基础中的基础，分值稳定，不会缺席。

---

六、易错点提醒

易错点1

• 错误表现：认为"度为2的有序树就是二叉树"
• 错误原因：忽略了二叉树的子树有严格的左右之分，而度为2的有序树只强调子树有序（可交换左右仍视为不同二叉树但同一棵树）
• 正确理解：二叉树的左右子树不可交换，交换后是不同的二叉树。即使只有一棵子树也必须标明是左还是右

易错点2

• 错误表现：计算完全二叉树深度时写成 $k = \lceil \log_2 n \rceil$
• 错误原因：混淆了 $\lfloor \log_2 n \rfloor + 1$ 和 $\lceil \log_2 n \rceil$。当 $n$ 恰好是2的幂时两者不同
• 正确理解：深度公式是 $k = \lfloor \log_2 n \rfloor + 1$。例如 $n=8$ 时 $k = 3+1 = 4$，而 $\lceil \log_2 8 \rceil = 3$，结果不同

易错点3

• 错误表现：认为完全二叉树中 $n_1$ 一定为0
• 错误原因：混淆了满二叉树和完全二叉树。满二叉树 $n_1=0$，但完全二叉树 $n_1$ 可以为0或1
• 正确理解：完全二叉树的 $n_1$ 取决于 $n$ 的奇偶性：$n$ 为奇数时 $n_1=0$，$n$ 为偶数时 $n_1=1$

易错点4

• 错误表现：在运用性质3时，误以为 $n_0 = n_2 + 1$ 中包含度为1的节点
• 错误原因：没有理解公式的推导过程
• 正确理解：$n_0 = n_2 + 1$ 与 $n_1$ 无关，这是一个普适公式，对任何二叉树都成立

---

七、来源标注

• 依据2026考研统考408大纲
• 依据《数据结构（C语言版）》严蔚敏版
• 依据《数据结构》王道考研辅导讲义