一、树的定义与基本概念
1. 树的定义
- 树是 n (n≥0) 个结点的有限集合。
- 非空树有且只有一个根结点。
- 其余结点分为 m (m>0) 个互不相交的集合 T₁, T₂, …, Tₘ，每个集合本身又是一棵树（子树）。
- 结点 T 称为 Tᵢ 的父结点，Tᵢ 称为 T 的子结点。
2. 树的特点
- 最适合表示具有分支层次关系的数据（如目录结构、组织架构）。
- 每个结点最多只有一个直接前驱（父结点）。
3. 结点的度
- 一个结点的子结点个数称为该结点的度。
- 树的度是树中所有结点度的最大值。
二、二叉树核心性质
1. 二叉树与树的区别
- 二叉树每个结点最多两棵子树，且子树有左右之分，顺序不能颠倒。
- 树不区分左右子树。
- 2 个结点能构造 2 种不同的二叉树：左孩子为根、右孩子为空；右孩子为根、左孩子为空。
2. 二叉树基本性质
| 性质 | 内容 |
|---|---|
| 性质1 | 第 i 层最多 2ⁱ⁻¹ 个结点（i≥1） |
| 性质2 | 深度为 k 的二叉树最多 2ᵏ - 1 个结点 |
| 性质3 | 终端结点数（叶子数）n₀ = 度为 2 的结点数 n₂ + 1 |
| 性质4 | n 个结点的完全二叉树深度为 ⌊log₂n⌋ + 1 |
| 性质5 | 完全二叉树按层编号：i 的双亲为 ⌊i/2⌋，左孩子为 2i，右孩子为 2i+1 |
3. 满二叉树
- 深度为 k 且结点数为 2ᵏ - 1。
- 每层都是满的，不存在度为 1 的结点。
- 所有叶子结点在同一层。
4. 完全二叉树
- 除最后一层外各层全满，最后一层结点从左向右连续排列。
- 若一个结点没有左孩子，则它必是叶子结点。
三、二叉树的存储结构
1. 顺序存储
- 用一维数组按层序存放，适合完全二叉树。
- 一般二叉树用顺序存储浪费空间大。
2. 链式存储（二叉链表）
- 每个结点含：左指针域、右指针域、数据域。
- 根结点的右指针为空（在二叉链表中，右指针指向右子树；根结点无兄弟，孩子兄弟表示法中右指针才指兄弟）。
3. 树的三种存储形式
| 存储形式 | 说明 |
|---|---|
| 双亲表示法 | 每个结点存其父结点位置 |
| 孩子链表表示法 | 每个结点存其所有子结点的链表 |
| 孩子兄弟表示法（二叉链表表示法） | 左指针指第一个孩子，右指针指下一个兄弟 |
- 顺序存储表示法不是树的常用存储形式（因树结构不规则，顺序存储浪费空间）。
四、二叉树的遍历
1. 三种遍历方式
| 遍历 | 顺序 | 递归实现 |
|---|---|---|
| 先序（前序） | 根 → 左子树 → 右子树 | 访问根，递归左，递归右 |
| 中序 | 左子树 → 根 → 右子树 | 递归左，访问根，递归右 |
| 后序 | 左子树 → 右子树 → 根 | 递归左，递归右，访问根 |
2. 遍历的重要性质
- 叶子结点在先序、中序、后序遍历中的相对次序不发生改变（永远从左到右）。
- 中序遍历中，A 在 B 前的条件是 A 在 B 的左方（A 是 B 左子树中的结点，或 B 在 A 的右子树中）。
- 中序遍历递归算法的平均空间复杂度为 O(n)（递归栈深度，最坏 n 层）。
3. 由遍历序列推导二叉树（通用方法）
核心条件：已知 先序 + 中序 或 后序 + 中序 可唯一确定二叉树。
已知 先序 + 后序 不能唯一确定（真二叉树除外）。
通用步骤（先序+中序为例）：
- 从先序第一个字符定根结点。
- 在中序中找到该根，左边为左子树中序，右边为右子树中序。
- 按左子树结点数在先序中划分出左右子树的先序序列。
- 递归重复。
举例（第15题）：先序 BEFCGDH，中序 FEBGCHD，求后序。
- 根：B。
- 中序：B 左边 FE → 左子树中序 FE；右边 GCHD → 右子树中序 GCHD。
- 先序中左子树部分：EF（长度2），右子树：CGDH（长度4）。
- 左子树：先序 EF，中序 FE → 根 E，E 左 F。左子树后序：FE。
- 右子树：先序 CGDH，中序 GCHD → 根 C，中序 C 左边 G，右边 HD。右子树先序：G, DH。G 直接是左孩子；右部分先序 DH，中序 HD → 根 D，D 左 H。右子树后序：G H D C。
- 整树后序：左子树后序 + 右子树后序 + 根 = FE + GHDC + B = F E G H D C B。
五、树、森林与二叉树的转换
1. 树转二叉树的规则（孩子兄弟表示法）
- 左指针指向该结点的第一个孩子。
- 右指针指向该结点的下一个兄弟。
- 转换后，根结点的右子树一定为空（根没有兄弟）。
- 树的后根遍历序列 = 对应二叉树的中序序列。
2. 森林转二叉树的规则
- 森林中第一棵树的根作为转换后二叉树的根。
- 第一棵树的子树森林转为左子树。
- 其余树构成的森林转为右子树。
3. 森林与二叉树结点关系（重点）
设森林 F 对应二叉树 B，B 有 m 个结点，B 的根为 p，p 的右子树结点数为 n：
- 根 p 对应森林第一棵树的根。
- 右子树（n 个结点）对应森林中除第一棵树外的其他所有树。
- 左子树 + 根（m - n 个结点）对应森林中第一棵树的全部结点。
- 因此：森林中第一棵树的结点数 = m - n。
4. 森林转二叉树右指针域为空的结点数
结论：森林 F 中有 n 个非终端结点，转成的二叉树 B 中右指针域为空的结点有 n+1 个。
推导：
- 森林中每个非终端结点，其最后一个孩子没有右兄弟，转换后该孩子的右指针为空。
- n 个非终端结点贡献 n 个空右指针域。
- 此外，二叉树的根结点没有兄弟，右指针也为空 → 加 1 个。
- 总共：n + 1 个。
六、哈夫曼树（Huffman Tree）
1. 定义
- 带权路径长度（WPL）最小的二叉树，权值越大的叶子离根越近。
2. 带权路径长度计算
- WPL = Σ (叶子权值 × 叶子到根的路径长度)。
3. 构造方法
- 将所有权值作为单结点树，放入森林。
- 选取两个权值最小的树作为左右子树，构造新二叉树，新树根权值为两子树权值之和。
- 重复步骤2，直到只剩一棵树。
举例（第14题）：权值 {3, 2, 4, 5, 1}
- 选1,2 → 和3；当前集合 {3, 3, 4, 5}
- 选3,3 → 和6；当前 {4, 5, 6}
- 选4,5 → 和9；当前 {6, 9}
- 选6,9 → 和15
- 树构造完毕，WPL = 1×3 + 2×3 + 3×2 + 4×2 + 5×2 = 3+6+6+8+10 = 33。
七、易错判断题辨析
| 判断内容 | 正误 | 要点 |
|---|---|---|
| 由二叉树先序和后序序列可唯一确定一棵二叉树 | 错 | 必须中序参与才能唯一确定 |
| 由树转换成二叉树，根结点的右子树一定为空 | 对 | 根无兄弟，右指针永远空 |
| 满二叉树中存在度为1的结点 | 错 | 满二叉树只有度为0和度为2的结点 |
| 任意二叉树终端结点数 = 度为2的结点数 + 1 | 对 | 二叉树性质3 |
八、知识速记卡
- 树：有且仅有一个根，子树互不相交。
- 二叉树性质：n₀ = n₂ + 1；满二叉树无度为1的结点。
- 存储：二叉链表根右指针为空；树存储有双亲、孩子链表、孩子兄弟三种。
- 遍历：叶子相对次序不变；中序A在B前⇔A在B左方；递归空间O(n)。
- 推导二叉树：需要先序+中序或后序+中序。
- 树→二叉树：后根遍历=二叉树中序；根右子树必空。
- 森林→二叉树：第一棵树结点数 = m - n（总结点 - 右子树结点）。
- 空右指针：非终端结点数 n + 1。
- 哈夫曼树：每次取最小两权值合并，WPL=Σ权值×路径长度。