13.3.7 其他特殊的二叉树
本节字幕实际延续最优二叉树，重点讲哈夫曼编码。为了和本页标题保持一致，这里先把哈夫曼编码讲透，再补充几个常见特殊二叉树的边界。
定长编码与变长编码
如果有 8 个字符，用定长二进制编码，至少需要 3 位，因为
哈夫曼编码属于变长编码：出现频率高的字符用短编码，出现频率低的字符用长编码，从而压缩整体长度。
| 编码方式 | 优点 | 缺点 | 适用 |
|---|---|---|---|
| 定长编码 | 解码简单，位置固定 | 高频字符也占同样长度，可能浪费 | 字符分布均匀、简单场景 |
| 哈夫曼变长编码 | 高频短码，平均长度低 | 需要构造树和保存编码表 | 频率差异明显的压缩场景 |
哈夫曼编码怎么从树上读
构造好哈夫曼树后，在每条边上标注 0 或 1。从根到某个叶子节点经过的边标记连起来，就是该字符的编码。
mermaid
flowchart TD
R["root"] -->|0| A["高频字符"]
R -->|1| B["内部节点"]
B -->|0| C["中频字符"]
B -->|1| D["低频字符"]例如上图中：
| 字符 | 编码 |
|---|---|
| 高频字符 | 0 |
| 中频字符 | 10 |
| 低频字符 | 11 |
左右标 0/1 不是绝对固定
课程特别提醒：左边是否一定标 0，不是绝对规定。有的题约定左 0 右 1，有的题可能用左 1 右 0；有的构造过程中相同权值还可以左右交换。因此同一组权值可能有多个合法哈夫曼编码。
考试处理方式：
- 先按题干约定标 0/1。
- 若题干未明确，结合选项判断可能采用的左右标注。
- 相同权值左右交换会改变具体编码，但不改变 WPL。
- 判断“是不是哈夫曼编码”时，更重要的是是否前缀无歧义、是否来自合法树形。
哈夫曼编码为什么能无歧义
哈夫曼编码是前缀编码：任何一个字符的编码都不是另一个字符编码的前缀。因为字符只放在叶子节点上，不放在内部节点上；从根到叶形成完整路径后，不会再继续向下接出另一个字符。
| 编码集合 | 是否前缀无歧义 | 原因 |
|---|---|---|
0, 10, 11 | 是 | 没有一个码字是另一个的前缀 |
0, 01, 11 | 否 | 0 是 01 的前缀 |
特殊二叉树边界补充
| 类型 | 核心边界 | 常见误区 |
|---|---|---|
| 满二叉树 | 每一层都满 | 只看最后一层满不够 |
| 完全二叉树 | 最后一层可以不满，但必须从左连续 | 中间缺节点就不是完全二叉树 |
| 二叉排序树 | 左小右大，中序有序 | 先序/后序不保证有序 |
| 哈夫曼树 | WPL 最小 | 形态不唯一，编码也可能不唯一 |
| 平衡二叉树 | 控制左右子树高度差 | 不是所有二叉排序树都平衡 |
技术迭代：哈夫曼编码为什么替代简单定长编码
| 方案 | 问题 | 改进动机 |
|---|---|---|
| 定长编码 | 不区分高频和低频字符 | 频率差异大时平均码长可优化 |
| 普通变长编码 | 可能出现前缀冲突，解码歧义 | 需要前缀无歧义 |
| 哈夫曼编码 | 构造和维护编码表较复杂 | 用最小 WPL 保证平均编码长度尽可能低 |
哈夫曼编码不是让每个字符都更短，而是让“按出现频率加权后的平均长度”更短。
本节例题
哈夫曼编码能够无歧义解码，关键在于：
自查清单
- 能否说明定长编码和哈夫曼变长编码的取舍？
- 能否从哈夫曼树读出某个字符编码？
- 能否解释为什么左右标 0/1 或相同权值交换会影响具体编码？
- 能否判断一组编码是否满足前缀无歧义？