DS-3 树与二叉树

这一部分为什么存在？

线性结构表达不了“一个元素有多个后继”的层次关系。树的主线问题链：

1. 层次关系怎么定义和度量：度、深度、高度、结点数之间有什么铁律（性质题的来源）；
2. 怎么存：链式（二叉链表，通用）vs 顺序（数组下标隐含父子关系，仅适合完全二叉树——2020-3：高度 5 的树顺序存储至少要 $2^5-1=31$ 个单元，浪费一目了然）；
3. 怎么访问每一个结点（遍历）：四种遍历不是四种背法，而是“根在什么时候被访问”的四种选择，且递归遍历的本质是栈（接 DS-2）；
4. 遍历的副产品：递归遍历要系统栈，能不能把遍历顺序“刻”在树上省掉栈 → 线索二叉树；
5. 更一般的树和森林怎么办：孩子-兄弟表示法统一转成二叉树处理（化未知为已知）；
6. 树还能优化什么：带权路径长度最小 → 哈夫曼树（最优前缀编码）；集合的合并与查找 → 并查集。

flowchart TD
    A["一对多的层次关系"] --> B["树的定义与基本术语<br/>度 / 深度 / 高度"]
    A --> C["二叉树：每个结点 ≤ 2 个孩子<br/>+ 五条性质"]
    C --> D["存储：二叉链表 / 顺序存储"]
    C --> E["遍历：先 / 中 / 后 / 层序<br/>（根何时被访问）"]
    E --> F["由两个序列重建唯一二叉树<br/>（必须含中序）"]
    E --> G["遍历要栈 → 线索二叉树<br/>空指针改指前驱/后继"]
    A --> H["树 / 森林 ↔ 二叉树<br/>孩子-兄弟表示法"]
    C --> I["应用：哈夫曼树<br/>WPL 最小 = 最优前缀编码"]
    C --> J["应用：并查集<br/>集合的并 / 查"]

核心概念（性质五条，选择题弹药库）：

• 2011-4：768 结点完全二叉树 → 叶 384（$n_0=n_2+1$ 与 $n = n_0+n_1+n_2$ 联立，完全二叉树 $n_1 \in \{0,1\}$）。
• 2009-5：第 6 层 8 个叶的完全二叉树最多 111 个结点。
• 2016-5：森林 25 结点 15 边 → 树的棵数 = 25−15 = 10（每棵树结点数 = 边数+1）。

1. 遍历：递归、重建与“序列反推”题型

四种遍历：先序（根左右）、中序（左根右）、后序（左右根）、层序（队列，BFS 的树版）。递归代码三行：

void InOrder(BiTree T) {
    if (T == NULL) return;
    InOrder(T->lchild);
    visit(T);                    // 先序：提到最前；后序：放到最后
    InOrder(T->rchild);
}

重建定理：先序 + 中序、或后序 + 中序可唯一确定二叉树；先序 + 后序不能（无法分左右，2011-5、2012-3 考的就是这个“不能”及由此推出的受限结论）。重建步骤：先序首元素定根 → 在中序中定位根 → 左段递归左子树、右段递归右子树。

常见变体：先序序列为 $a,b,c,d$ 的不同二叉树个数 = 卡特兰数 $C_4 = 14$（2015-2）；“先序与中序相同”的条件 = 所有非叶结点只有右孩子（2017-4）；由后序序列 + 树形局部信息推先序（2023-5、2017-5）。

2. 线索二叉树：把遍历顺序刻进空指针

为什么存在：二叉链表 $n$ 个结点有 $n+1$ 个空指针（性质 3 的推论），遍历找前驱/后继又要栈——不如让空指针就地指向前驱/后继（左指针 → 前驱，右指针 → 后继），并用 ltag/rtag 区分孩子与线索。考法是给树识线索或反之：2014-4（中序线索化后 x 的左右线索指向）、2013-5（后序线索树中叶结点 X 的右线索 = 其后序后继，即 X 存在左兄弟 Y 时指向父结点）、2010-3（识别合法的后序线索树）。

3. 树、森林与二叉树的转换

孩子-兄弟表示法：每个结点存“第一个孩子 + 下一个兄弟”→ 任意树/森林统一成二叉链表。转换规则的记忆钩：“左孩子右兄弟”。

对应遍历关系（高频，2019-2、2020-4、2021-4）：

相关真题：2011-6（2011 结点的树叶 116 → 对应二叉树中无右孩子结点数：无右孩子 ⟺ 原树中该结点是其父的“最小孩子”，叶是最小孩子的情况 + …，标准解 115+1？——此类题按“无右兄弟”定义逐类计数）；2014-5（森林叶结点数与二叉树中“无左孩子结点数”相等）。

4. 哈夫曼树与哈夫曼编码

问题：字符出现频率不同，怎么编码使电文总长最短？直觉：高频用短码——但要保证前缀无关（任何编码不是另一个的前缀，否则无法切分译码），而二叉树的叶结点编码天然前缀无关。于是问题 = 构造 WPL（带权路径长度）最小的二叉树。

构造：每次取权值最小的两棵树合并，新根权 = 两者之和，放回集合，重复到只剩一棵。$n$ 个叶 → $n-1$ 次合并 → 总结点 $2n-1$（2019-3：115 结点 → $n=58$）。

考点家族：WPL 计算（2021-5：{10,12,16,21,30} → 200）、编码可能性判断（2018-5：合并过程约束下的合法编码）、译码（2017-6：按位走树，到叶输出字符再回根）、性质辨析（2010-6：哈夫曼树不一定是完全二叉树；2022-5：与定长编码树对比——不同频次的字符在哈夫曼树中处于不同层？不一定，看合并结果；定长编码所有叶同层）。加权平均长度 = WPL / 总频次（2023-4）。

5. 并查集（识别思想 + 会模拟）

用双亲数组表示森林：每个集合一棵树，根即集合代表。Find(x) 沿父链找根；Union(x,y) 把一棵根挂到另一棵根下。优化：按秩合并（小树挂大树）+ 路径压缩（Find 时沿途直接挂根）。应用：Kruskal 判环（DS-4）、等价类划分。

先序/中序/后序 vs 层序（易混对）：前三种是 DFS（栈/递归），层序是 BFS（队列）——一道题的判断：序列中“同层相邻”是层序；根的位置（首/中/尾）定 DFS 三序。

哈夫曼树 vs 二叉排序树：为什么易混——都是“为某种最优性构造的二叉树”。本质区别——哈夫曼优化叶结点带权路径（数据在叶、用于编码），BST 优化查找路径（数据全在、中序有序）。判别线索：题目出现“频次/编码/WPL”→ 哈夫曼；“查找/中序有序”→ BST（DS-5）。

形态一：性质计算：2009-5、2011-4、2016-5、2018-4（满二叉树 $2k-1$）、2020-3（顺序存储单元数）。

形态二：遍历序列互推：2009-3（由序列认遍历方式）、2011-5、2012-3（先+后不能定）、2015-2（卡特兰 14）、2017-4/5、2020-4、2021-4、2022-3（中序相邻两点的关系排除）、2023-5。

形态三：线索二叉树：2010-3、2013-5、2014-4。

形态四：树/森林转换：2009-6、2011-6、2014-5、2016-5、2019-2、2021-4。

形态五：哈夫曼：2010-6、2015-3、2017-6、2018-5、2019-3、2021-5、2022-5、2023-4。

形态六（与 DS-7 衔接）：树类代码大题：2014-41（WPL：任一 DFS 中记录深度累加叶权）、2017-41（表达式树转中缀：递归 + 括号层级判断）、2022-41（顺序存储判定 BST：中序递增 / 递归上下界）——树类模板详见 DS-7。

做题触发词：看到“完全二叉树 + 结点数”→ 性质 3/5 联立；看到“先序+后序”→ 立即警觉不能唯一确定；看到“线索”→ 先确认是哪种次序的线索树；看到“频次/编码”→ 哈夫曼合并模拟；看到“后根遍历”→ 转二叉树中序。

来源：真题markdown/2009-2024统考真题.md 对应题号。

• 向前依赖：DS-2（递归遍历的本质是栈；层序的本质是队列）。
• 向后引出：
  • 中序遍历 + 有序 = BST 的中序特性 → DS-5 查找（AVL、红黑树、B 树都是“树 + 排序约束”）；
  • 哈夫曼的最优合并思想 → DS-6 外部排序的最佳归并树；
  • 并查集 → DS-4 Kruskal；
  • 跨学科：目录树（OS-7）、多级页表（OS-5）、前缀码与路由查找（CN-3，2020-42 前缀编码大题即哈夫曼/前缀树思想）、DNS 域名树（CN-5）——X-8。

1. 为什么线性结构表达不了目录结构？（一对多 → 树）
2. 二叉树最重要的性质是哪条？怎么用它算叶结点数？（$n_0 = n_2 + 1$）
3. 完全二叉树为什么适合数组存？一般树为什么不适合？
4. 四种遍历的本质区别是什么？（根何时访问；DFS 用栈、层序用队列）
5. 哪两种遍历序列能唯一重建一棵树？为什么必须含中序？
6. 递归遍历要栈，能不能免栈？（线索二叉树：空指针指前驱/后继）
7. 任意的树/森林怎么统一处理？（孩子-兄弟 → 二叉树）
8. 树的先根/后根遍历分别对应二叉树的什么遍历？
9. 为什么二叉树的叶编码天然前缀无关？
10. 哈夫曼树怎么构造？为什么它 WPL 最小？$n$ 个叶共几个结点？
11. 并查集怎么表示集合？两个优化各降什么代价？
12. 树类代码大题的通用骨架是什么？（递归 + 全局量/参数传递——接 DS-7）