什么是 Huffman树？

哈夫曼树（Huffman Tree），又叫“最优二元树”，它的核心思想非常简单，可以用一句话概括：“大权值靠近根，小权值远离根”。这样做也是为了让总的“代价”最小。

做这类题，甚至不需要死记硬背复杂的代码逻辑，只要掌握“排、取、加、放”这四个字的口诀即可。

下面我通过一个具体的例子一步步做。

一、 核心步骤

  1. 排：把所有还没有处理的数字（权值）从小到大排列。
  2. 取：取出最小的两个数字。
  3. 加：把这两个数字相加，得到一个新的数字（父节点）。
  4. 放：把这个新的数字放回刚才的队伍里，并把之前那两个取出来的数字删掉。
  5. 循环：重复上面的步骤，直到队伍里只剩下一个数字（这个数字就是树的根）。

二、 手把手演示

题目：有一组权值 W = {2, 3, 6, 8, 9}，请构建哈夫曼树，并计算带权路径长度 (WPL)。

第一轮：

  1. 排：目前池子里是 {2, 3, 6, 8, 9} (已经有序)。
  2. 取：最小的俩是 2 和 3。
  3. 加：2 + 3 = 5。
  4. 放：把 5 放回去。此时池子变成了 {5, 6, 8, 9}（注意：2和3已经用掉了，变成了5的左右孩子）。

第二轮：

  1. 排：池子是 {5, 6, 8, 9}。
  2. 取：最小的俩是 5 和 6。
  3. 加：5 + 6 = 11。
  4. 放：把 11 放回去。此时池子变成了 {8, 9, 11}。

第三轮：

  1. 排：池子是 {8, 9, 11}。（注意这里顺序很重要，11比8和9都大，所以在后面）。
  2. 取：最小的俩是 8 和 9。
  3. 加：8 + 9 = 17。
  4. 放：把 17 放回去。此时池子变成了 {11, 17}。

第四轮：

  1. 排：池子是 {11, 17}。
  2. 取：最小的俩是 11 和 17。
  3. 加：11 + 17 = 28。
  4. 放：只剩下一个 28 了，结束。28 就是树根。

三、 怎么把刚才的过程画成树？

根据刚才的计算过程，我们可以倒推画图：

  1. 根是 28，它的两个孩子是 11 和 17。
  2. 17 是由 8 和 9 变来的，所以 17 下面挂着 8 和 9。
  3. 11 是由 5 和 6 变来的，所以 11 下面挂着 5 和 6。
  4. 5 是由 2 和 3 变来的，所以 5 下面挂着 2 和 3。

结构图大致如下：

1
2
3
4
5
6
7
       28
      /  \
    11    17
   /  \  /  \
  5    6 8   9
 / \
2   3

(通常二叉树左边画小的，右边画大的，但这不影响最终的WPL计算结果)

四、 怎么计算带权路径长度 (WPL)？

有两种算出来的结果是一模一样的，这里有一个笨办法和一个聪明办法。

笨办法：公式定义法

WPL = ∑(叶子节点的权值 × 它走的层数/步数)

看图： * 2: 走了3步 (28->11->5->2)。代价 = 2 × 3 = 6 * 3: 走了3步。代价 = 3 × 3 = 9 * 6: 走了2步 (28->11->6)。代价 = 6 × 2 = 12 * 8: 走了2步。代价 = 8 × 2 = 16 * 9: 走了2步。代价 = 9 × 2 = 18

总 WPL = 6 + 9 + 12 + 16 + 18 = 61

聪明办法：所有非叶子节点之和

这是一个考场秒杀技巧。WPL 等于构建过程中所有产生出的“新节点”（和）的总和。

回顾刚才的计算过程：

  1. 第一次合成了 5
  2. 第二次合成了 11
  3. 第三次合成了 17
  4. 第四次合成了 28

直接相加：5 + 11 + 17 + 28 = 61。

(不管树画得多么歪七扭八，只要计算过程是对的，用这个办法算一定对！)

五、 避坑指南

  1. 一定要重新排序！
    • 很多人做错是因为合成了一个新数字后，这数字比较大，没有把它排到后面去，导致下一次取“最小两项”时取错了。
    • 比如：如果池子剩下 10, 20，合成了 30，而池子后面还有个 25。如果不重新排序，你可能就会拿 30 和 25 合并。但实际上应该先把 30 放后面，看有没有比它小的。
  2. 只算叶子节点
    • 题目给的原始数字（2, 3, 6, 8, 9）才是叶子，WPL 是算这些叶子的代价。中间产生的 5, 11, 17 只是过程量。

你按照这个逻辑去试试做一道题，是不是思路清晰多了？