这一篇重点解决408中最常见的过程题：遍历、由遍历序列还原二叉树、线索二叉树、树与森林转换、哈夫曼树和WPL。

---

一、四种遍历顺序

先序：根 左 右
中序：左 根 右
后序：左 右 根
层序：从上到下、从左到右

记忆：

先序根最先
中序根中间
后序根最后

例如：

        A
       / \
      B   C
     / \   \
    D   E   F

得到：

先序：A B D E C F
中序：D B E A C F
后序：D E B F C A
层序：A B C D E F

---

二、由遍历序列还原二叉树

1. 先序 + 中序

先序第一个元素一定是根。

在中序中找到根以后，中序被分成：

左子树 | 根 | 右子树

然后按照左右子树结点数量，再去切先序序列，递归完成。

固定模板：

先序找根
中序切左右
递归重建

2. 后序 + 中序

后序最后一个元素一定是根。

固定模板：

后序找根
中序切左右
递归重建

3. 先序 + 后序

一般不能唯一确定二叉树。

原因是：如果某结点只有一个孩子，单靠先序和后序无法判断这个孩子是左孩子还是右孩子。

结论：

先序 + 中序 -> 一般可唯一确定
后序 + 中序 -> 一般可唯一确定
先序 + 后序 -> 一般不能唯一确定

---

三、典型还原题

已知：

先序：A B D E C F
中序：D B E A C F

先序第一个A是根。

在中序中：

D B E | A | C F

所以左子树有3个结点，右子树有2个结点。

继续切先序：

左子树先序：B D E
右子树先序：C F

左子树中，B是根：

D | B | E

所以D是左孩子，E是右孩子。

右子树中，C是根：

C | F

所以C无左孩子，F是右孩子。

最终：

        A
       / \
      B   C
     / \   \
    D   E   F

---

四、层序遍历与队列

层序遍历必须想到队列：

根入队
取出队头
访问该结点
左孩子入队
右孩子入队
重复

所以：

层序遍历 -> 队列
DFS/递归遍历 -> 栈或递归

---

五、线索二叉树

线索二叉树的目的：

利用原本为空的孩子指针，保存遍历序列中的前驱和后继。

n个结点的二叉链表中：

总指针域 = 2n
真实孩子指针 = n-1
空指针 = n+1

因此可利用的原空指针一共有：

n+1

中序线索树常考

若某结点左指针为空：

可指向中序前驱

若右指针为空：

可指向中序后继

注意：线索指针不是孩子指针，必须结合标志位判断。

---

六、树和森林转换成二叉树

核心口诀：

左孩子，右兄弟

意思是：

第一个孩子 -> 二叉树中的左孩子
下一个兄弟 -> 二叉树中的右孩子

例如A有三个孩子B、C、D：

A.left = B
B.right = C
C.right = D

遍历对应关系

树的先根遍历 = 对应二叉树的先序遍历
树的后根遍历 = 对应二叉树的中序遍历

森林也有类似对应：

森林先序 = 对应二叉树先序
森林中序 = 对应二叉树中序

---

七、哈夫曼树

哈夫曼树解决的是：

带权路径长度 WPL 最小

构造规则只记一句：

每次从当前集合中取最小的两个权值合并。

合并出的新权值重新放回集合，继续选择最小两个。

---

八、WPL怎么算

WPL定义：

WPL = Σ(叶子权值 × 根到叶子的路径长度)

路径长度通常按“边数”计算。

快速算法

构造哈夫曼树时：

WPL = 每次合并所得新权值之和

例如权值：

2, 3, 7, 9

合并：

2+3=5
5+7=12
9+12=21

所以：

WPL = 5+12+21 = 38

不必画完整哈夫曼树也能直接算。

---

九、哈夫曼树结点数量

若有n个初始权值，也就是n个叶子：

叶子结点 = n
内部结点 = n-1
总结点 = 2n-1

因为哈夫曼树中不存在度为1的结点。

---

十、哈夫曼编码

在左右分支分别标记0和1，可以得到哈夫曼编码。

核心性质：

哈夫曼编码是前缀编码

也就是：

任何一个字符编码都不是另一个字符编码的前缀

所以可以唯一解码。

平均码长

若字符概率为pi，码长为li：

平均码长 = Σ(pi * li)

若给频数wi：

平均码长 = Σ(wi * li) / Σwi

其中：

Σ(wi * li) = WPL

---

十一、典型哈夫曼计算

权值：

5, 7, 10, 15, 20

依次合并：

5+7=12
10+12=22
15+20=35
22+35=57

因此：

WPL = 12+22+35+57
    = 126

有5个叶子，因此：

内部结点 = 4
总结点 = 9

---

十二、考试高频题型

给树 -> 求先中后层序遍历

给先序+中序 -> 还原树

给后序+中序 -> 还原树

问能否唯一确定 -> 看是否含中序

线索树 -> 问前驱、后继、空指针数量

树/森林转二叉树 -> 左孩子右兄弟

哈夫曼 -> 每次合并两个最小值

WPL -> 所有合并值之和

---

十三、高频失分点

1. 后序最后一个才是根，不是第一个。

2. 先序+后序一般不能唯一确定。

3. WPL的路径长度通常按边数，不要从根结点算1。

4. 哈夫曼每一轮都要重新从“当前集合”里选最小两个。

5. 线索指针不是实际孩子。

6. 树转二叉树一定记“左孩子，右兄弟”。

---

十四、10秒背诵版

先根左右，中左根右，后左右根；
先中能还原，后中能还原，先后一般不唯一；
线索空指针n+1；
树转二叉树：左孩子右兄弟；
哈夫曼两小合并；
WPL等于所有合并值之和；
n个叶子，总结点2n-1。