【408考研·数据结构专题】二叉树、树与森林、线索树及哈夫曼树核心考点与秒杀技巧深度总结

一、 二叉树的基本概念与形态推导

1. 二叉树的核心操作逻辑

• 基本操作：查找结点、删除二叉树结点、输出高度、统计结点数。

🎯核心方法总结：

• 左→ \rightarrow→右→ \rightarrow→根（后序思维）。
• 在树的性质及操作中，凡是涉及左右子树的部分，一般都要用到递归。

2. 卡特兰数（Catalan）与二叉树形态推导

对于长度为n nn的入栈序列，其可能产生的出栈序列数量，与n nn个结点所能构成的二叉树形态数量完全一致：

出栈序列数量 = 二叉树的形态数量 = C 2 n n n + 1 = ( 2 n ) ! n ! ( n + 1 ) ! \text{出栈序列数量} = \text{二叉树的形态数量} = \frac{C_{2n}^n}{n+1} = \frac{(2n)!}{n!(n+1)!}出栈序列数量=二叉树的形态数量=n+1C2nn​​=n!(n+1)!(2n)!​

二、 经典例题复盘：完全二叉树结点最值问题

📝 【例题】

完全二叉树第 5 层有 9 个叶子结点，则该树最多有 _____ 个结点。

🔍 【解析与推导过程】

1. 已知得：在满二叉树状态下，第 5 层原本应该有2 5 − 1 = 16 2^{5-1} = 1625−1=16个结点。
2. 现在题干指出第 5 层有9 个是叶子结点（这意味着这 9 个结点已被确认在下一层无子结点）。
3. 因此，第 5 层还剩下16 − 9 = 7 16 - 9 = 716−9=7个非叶子结点可以向下延伸长出子女。
4. 为了让整棵树的结点数最多，这 7 个非叶子结点在第 6 层必须全部长满，即在第 6 层最多拥有7 × 2 = 14 7 \times 2 = 147×2=14个结点。
5. 总结点数计算：前 4 层满结点数 + 第 5 层结点数 + 第 6 层最大结点数

最多结点数 = 7 × 2 + 16 + 8 + 4 + 2 + 1 = 14 + 24 + 7 = 45 \text{最多结点数} = 7 \times 2 + 16 + 8 + 4 + 2 + 1 = 14 + 24 + 7 = 45最多结点数=7×2+16+8+4+2+1=14+24+7=45

• 答案：45

三、 二叉树的遍历方法与还原技巧

1. 三大基础遍历逻辑

• 先序遍历：根→ \rightarrow→左→ \rightarrow→右
• 中序遍历：左→ \rightarrow→根→ \rightarrow→右
• 后序遍历：左→ \rightarrow→右→ \rightarrow→根

🎯核心方法总结：
遍历的遍历顺序可以理解为根的遍历顺序不同：

• 先序—— 根先
• 中序—— 根中
• 后序—— 根后

注：无论哪种遍历，左子树永远在右子树前面访问。

2. 实例深度分析

针对经典二叉树拓扑结构，其遍历序列具体表现如下：

• 先序序列：1 → 2 → 4 → 7 → 5 → 8 → 3 → 6 → 9 → 10 1 \rightarrow 2 \rightarrow 4 \rightarrow 7 \rightarrow 5 \rightarrow 8 \rightarrow 3 \rightarrow 6 \rightarrow 9 \rightarrow 101→2→4→7→5→8→3→6→9→10

• 特性观察：易见先序序列是图中的多个连续段。

• 中序序列：7 → 4 → 2 → 5 → 8 → 1 → 3 → 9 → 6 → 10 7 \rightarrow 4 \rightarrow 2 \rightarrow 5 \rightarrow 8 \rightarrow 1 \rightarrow 3 \rightarrow 9 \rightarrow 6 \rightarrow 107→4→2→5→8→1→3→9→6→10

• 特性观察：易见中序序列到是三合一的一个模块（例如末尾的9, 6, 10构成小局部模块）。

• 后序序列：7 → 4 → 8 → 5 → 2 → 9 → 10 → 6 → 3 → 1 7 \rightarrow 4 \rightarrow 8 \rightarrow 5 \rightarrow 2 \rightarrow 9 \rightarrow 10 \rightarrow 6 \rightarrow 3 \rightarrow 17→4→8→5→2→9→10→6→3→1

🚀秒杀技巧：中序投影法
中序序列可用投影法速成：以左、根、右的相对几何位置向下作垂直投影，即可直接读出中序遍历结果。

3. 双序列恢复二叉树

• 可唯一确定二叉树的组合：【先序 + 中序】、【后序 + 中序】、【层次 + 中序】。

🎯核心方法总结：
以中序序列为划分基准（用于切分左右子树），另一序列（先序/后序/层次）为实际结点的层次（或确定当前的根节点）。

四、 线索二叉树（Threaded Binary Tree）

1. 线索二叉树的底层本质

• n nn个结点的二叉树，其二叉链表中必然含有n + 1 n+1n+1个空指针域。利用这些空指针域存放指向前驱和后继的指针，即为“线索”。
• 主要应用：① 找第一个和最后一个结点；② 找前驱；③ 找后继。

2. 线索化核心规则

🎯核心方法总结：
若无左子树，lchild指向前驱；若无右子树，rchild指向后继。
所以只需要考虑叶子结点（及缺少单侧子树的结点）。

3. 各种遍历下的线索流向趋势

• 先序方向：a -> b -> c -> d -> e
• 中序方向：b -> a -> d -> c -> e
• 后序方向：b -> d -> e -> c -> a

五、 树与森林的存储结构

1. 双亲表示法

• 实现方式：采用连续的数组存储，每个结点包含数据域与双亲结点的数组下标。
• 特点：易找双亲结点，不易删除结点。

【示例键值表】

2. 孩子表示法

• 实现方式：数组与单链表结合。数组存放各结点，链表存放该结点的所有孩子。

【示例链表结构】

• 0 [A]→ 1 → 2 → NULL \rightarrow 1 \rightarrow 2 \rightarrow \text{NULL}→1→2→NULL
• 1 [B]→ 3 → NULL \rightarrow 3 \rightarrow \text{NULL}→3→NULL
• 2 [C]→ NULL \rightarrow \text{NULL}→NULL
• 3 [D]→ 4 → NULL \rightarrow 4 \rightarrow \text{NULL}→4→NULL
• 4 [E]→ NULL \rightarrow \text{NULL}→NULL

3. 孩子兄弟表示法（二叉链表表示法）

🎯核心方法总结：
记住指针分配口诀：左指孩子，右指兄弟。

六、 树、森林与二叉树的转换及遍历对应

1. 转换规则

• 树⇒ \Rightarrow⇒二叉树：左指孩子，右指兄弟。
• 森林⇒ \Rightarrow⇒二叉树：左指孩子，右指兄弟。各棵树的根结点从左往右依次连接。

2. 树与森林的遍历序列示例（对应上述存储结构树）

• 树的先根遍历：A B D E C
• 树的后根遍历：E D B C A

3. 🌟 核心对应关系表（重中之重）

七、 哈夫曼树（Huffman Tree）

1. 核心定义

哈夫曼树是指带权路径长度（WPL）最小的二叉树。

2. 基础概念拆解

1. 权（Weight）：给结点赋予的具有某种特定实际意义的数值。
2. 路径长度：该结点到根结点的跳数。
3. 带权路径长度（WPL）：所有叶子结点到根结点的带权跳数（即：叶子结点的权值× \times×路径长度）之和。