13.3.6 最优二叉树

最优二叉树在软考中通常等同于哈夫曼树。它的目标是：给定一组权值，构造一棵带权路径长度最小的二叉树。它最典型的应用是哈夫曼编码。

基本概念

概念	含义
路径长度	从根到某节点经过的分支数
权值	节点代表对象的重要程度、频率或概率
带权路径长度	节点权值 × 从根到该节点的路径长度
树的带权路径长度 WPL	所有叶子节点带权路径长度之和
最优二叉树	WPL 最小的二叉树

公式：

$$WPL=\sum _{i=1}^n{w}_i{l}_i$$

其中 $w_i$ 是第 $i$ 个叶子节点权值，$l_i$ 是它到根的路径长度。

为什么大权值要靠近根

WPL 中权值和路径长度相乘。若一个权值很大，却放在很深的地方，它会贡献很大的代价。为了让总成本最小，频率高/权值大的节点应靠近根，权值小的节点可以更深。

放置方式	结果
大权值靠近根	大权值乘较小路径长度，总成本低
大权值远离根	大权值乘较大路径长度，总成本高

哈夫曼树构造算法

课程给出的构造方法是贪心：

1. 在当前权值集合中选出最小的两个。
2. 把它们合并成一棵子树，新根权值为二者之和。
3. 从集合中删除这两个权值，加入新权值。
4. 重复，直到只剩一棵树。

flowchart TD
  A["权值集合"] --> B["取最小两个"]
  B --> C["合并为新节点"]
  C --> D["删除旧权值，加入权值和"]
  D --> E{"只剩一个根？"}
  E -->|否| B
  E -->|是| F["得到哈夫曼树"]

构造示例：1、2、4、8

1. 取 1 和 2 合并为 3。
2. 取 3 和 4 合并为 7。
3. 取 7 和 8 合并为 15。

这样权值 8 距离根更近，权值 1、2 更远，总 WPL 更小。

构造形态不唯一

如果最小权值中有相同值，左右位置可以交换；合并时遇到并列选择，也可能得到不同形态。但只要每一步都满足“取最小两个合并”，最终 WPL 是最小的。

这也是考试中需要结合选项判断编码的原因：树形不同、左右边标注不同，具体编码可能不同，但总代价相同。

哈夫曼树考法

考法	做题方法
判断 WPL	找叶子权值和路径长度，逐项相乘求和
构造哈夫曼树	每一步选最小两个，合并后重新排序
判断是否最优	看是否符合最小两两合并原则，或比较 WPL
哈夫曼编码	根据树上 0/1 标注，从根到叶读路径

本节例题

单选

构造哈夫曼树时，每一步应当：

A每次选最大的两个权值合并B每次任选两个权值合并C每次选最小的两个权值合并D先按输入顺序两两合并

自查清单

1. 能否计算一棵给定树的 WPL？
2. 能否按“最小两个合并”完整构造哈夫曼树？
3. 能否解释为什么权值大的叶子更靠近根？