Appearance
树与二叉树的定义与基本概念
核心思想
树的定义
树（Tree）是 n（n ≥ 0）个结点的有限集合 T。当 n = 0 时为空树；当 n > 0 时满足：
- 有且仅有一个特定的结点称为根（root）
- 其余结点可分为 m（m ≥ 0）个互不相交的有限集合 T₁, T₂, ..., Tₘ，每个集合本身又是一棵树，称为根的子树（subtree）
这是一个递归定义——树的定义中包含了树自身。
基本术语
A ← 根结点（第1层）
/ | \
B C D ← 第2层
/ \ / \
E F G H ← 第3层
/
I ← 第4层| 术语 | 定义 | 上图示例 |
|---|---|---|
| 结点的度 | 结点的子树个数 | A 的度 = 3，B 的度 = 2，C 的度 = 0 |
| 树的度 | 树中结点的最大度数 | 度 = 3（结点 A） |
| 叶子结点 | 度为 0 的结点 | C, E, G, H, I |
| 分支结点 | 度 > 0 的结点 | A, B, D, F |
| 孩子与双亲 | 结点的子树的根称为孩子，该结点称为双亲 | B 是 A 的孩子，A 是 B 的双亲 |
| 兄弟 | 同一双亲的结点 | B、C、D 互为兄弟 |
| 祖先与子孙 | 从根到该结点路径上的所有结点 | I 的祖先：F、B、A |
| 结点的层次 | 根为第 1 层，其孩子为第 2 层，依次类推 | I 在第 4 层 |
| 树的高度（深度） | 树中结点的最大层次 | 高度 = 4 |
| 有序树/无序树 | 子树从左到右有无次序之分 | — |
| 森林 | m（m ≥ 0）棵互不相交的树的集合 | 删去根 A 后得到 3 棵子树构成的森林 |
树的性质
| 性质 | 公式 |
|---|---|
| 结点数 = 所有结点的度之和 + 1 | n = Σdegree + 1 |
| 度为 m 的树第 i 层最多有 mⁱ⁻¹ 个结点 | — |
| 高度为 h 的 m 叉树最多有 (mʰ - 1)/(m - 1) 个结点 | 等比数列求和 |
| n 个结点的 m 叉树最小高度 | h = ⌈logₘ(n(m-1) + 1)⌉ |
二叉树的定义
二叉树（Binary Tree）是 n（n ≥ 0）个结点的有限集合，它或者是空集，或者由一个根结点和两棵互不相交的、分别称为左子树和右子树的二叉树组成。
二叉树与度为 2 的有序树的区别：
| 二叉树 | 度为 2 的有序树 | |
|---|---|---|
| 子树数量 | 每个结点最多 2 棵子树 | 恰好存在度为 2 的结点 |
| 空树 | 可以是空树 | 至少有 3 个结点 |
| 左右之分 | 严格区分左右子树 | 只有一棵子树时无左右之分 |
这是 408 的经典易错点——二叉树不是度为 2 的有序树的特例。
特殊二叉树
| 名称 | 定义 | 特点 |
|---|---|---|
| 满二叉树 | 高度为 h，有 2ʰ - 1 个结点 | 每层结点数都达到最大值 |
| 完全二叉树 | 前 h-1 层满，第 h 层从左到右连续 | 编号与满二叉树一一对应 |
| 二叉排序树（BST） | 左子树 < 根 < 右子树 | 中序遍历得到有序序列 |
| 平衡二叉树（AVL） | 任意结点左右子树高度差不超过 1 的 BST | 保证查找效率 O(log n) |
满二叉树 完全二叉树 非完全二叉树
1 1 1
/ \ / \ / \
2 3 2 3 2 3
/ \ / \ / \ \ / \
4 5 6 7 4 5 6 4 7二叉树的性质
这些性质是 408 计算题的核心工具：
| 编号 | 性质 | 公式 |
|---|---|---|
| 1 | 第 i 层最多有 2ⁱ⁻¹ 个结点 | — |
| 2 | 高度为 h 的二叉树最多有 2ʰ - 1 个结点 | — |
| 3 | 叶子数与度为2的结点数的关系 | n₀ = n₂ + 1 |
| 4 | n 个结点的完全二叉树高度 | h = ⌈log₂(n + 1)⌉ 或 ⌊log₂n⌋ + 1 |
| 5 | 完全二叉树结点 i 的双亲 | ⌊i/2⌋ |
| 6 | 完全二叉树结点 i 的左孩子 | 2i（若 2i > n 则无左孩子） |
| 7 | 完全二叉树结点 i 的右孩子 | 2i + 1（若 2i+1 > n 则无右孩子） |
性质 3 推导：设度为 0、1、2 的结点数分别为 n₀、n₁、n₂。从结点总数角度：n = n₀ + n₁ + n₂。从边的数量角度：边数 = n - 1 = n₁ + 2n₂。联立得 n₀ = n₂ + 1。
完全二叉树的额外性质
| 性质 | 说明 |
|---|---|
| n₁ 只能是 0 或 1 | n 为偶数时 n₁ = 1，n 为奇数时 n₁ = 0 |
| 叶子结点只出现在最后两层 | — |
| 度为 1 的结点最多 1 个 | 且该结点只有左孩子 |
树的存储结构
树不像二叉树那样最多两个孩子，结点的度不固定，因此需要专门的存储方式。
| 存储方式 | 结点结构 | 找双亲 | 找孩子 | 适用场景 |
|---|---|---|---|---|
| 双亲表示法 | data + parent（双亲在数组中的下标） | O(1) | O(n)，需遍历整个数组 | 以"找双亲"为主的应用（如并查集） |
| 孩子表示法 | 每个结点的孩子用单链表串联 | O(n)，需遍历所有链表 | O(度) | 以"找孩子"为主的应用 |
| 孩子兄弟表示法 | firstChild + nextSibling | 不方便（除非加 parent 指针） | O(度) | 树↔二叉树转换，详见树与森林的转换 |
双亲表示法
用一维数组存储所有结点，每个结点包含数据域和双亲下标：
下标 data parent
0 A -1 ← 根结点，parent = -1
1 B 0
2 C 0
3 D 0
4 E 1
5 F 1对应的树：A 是根，B/C/D 是 A 的孩子，E/F 是 B 的孩子。
孩子表示法
用数组存储所有结点，每个结点附带一个单链表，链表中存放该结点所有孩子的下标：
下标 data 孩子链表
0 A → [1] → [2] → [3] → ∧
1 B → [4] → [5] → ∧
2 C → ∧
3 D → ∧
4 E → ∧
5 F → ∧对比：双亲表示法和孩子表示法的优缺点正好互补。如果既需要找双亲又需要找孩子，可以将两者结合——在孩子表示法的基础上增加 parent 域。
二叉树的存储结构
| 存储方式 | 实现 | 适用场景 |
|---|---|---|
| 顺序存储 | 用数组，按完全二叉树编号存储 | 完全二叉树（空间利用率高） |
| 链式存储 | 二叉链表（lchild, data, rchild） | 一般二叉树 |
| 三叉链表 | 增加 parent 指针 | 需要频繁找双亲 |
含 n 个结点的二叉链表中，有 n + 1 个空指针域。推导：n 个结点共 2n 个指针域，其中 n - 1 个被使用（每条边占一个），剩余 2n - (n-1) = n + 1 个为空。这些空指针域正是线索二叉树利用的空间。
考研高频考点
- ⭐ 二叉树性质 n₀ = n₂ + 1 的计算应用（几乎每年必考）
- ⭐ 完全二叉树的结点数与高度的关系（选择题/填空题高频）
- ⭐ 完全二叉树的双亲/孩子编号计算（选择题）
- ⭐ 二叉树与度为 2 的有序树的区别（概念辨析）
- ⭐ 满二叉树与完全二叉树的区别（概念辨析）
- ⭐ 树的三种存储结构的特点对比：双亲表示法、孩子表示法、孩子兄弟表示法（选择题高频）
- 树的基本术语（度、层次、高度）的准确理解
- 空指针域个数 n + 1 的推导
- 森林与树的关系
易错：完全二叉树≠满二叉树。满二叉树是完全二叉树的特例，完全二叉树的最后一层可以不满，但结点必须从左到右连续排列。
易错：树的高度（深度）从 1 开始计数还是从 0 开始，不同教材有不同约定。408 统考通常采用根结点在第 1 层的约定（严蔚敏教材），做题时注意题目的具体定义。
相关知识
- 前序遍历、中序遍历、后序遍历：二叉树的三种递归遍历
- 层序遍历：利用队列的层次遍历
- 由遍历序列构造二叉树：前序+中序或后序+中序还原二叉树
- 线索二叉树：利用空指针域加速遍历
- 二叉排序树（BST）：动态查找的基本树结构
- 平衡二叉树（AVL）：保证最坏情况查找效率
- 哈夫曼树：最优前缀编码
- 树与森林的转换：树、森林、二叉树的相互转换