数据结构课讲到树这一章，绕不开哈夫曼树。压缩软件能把几百 MB 的日志压到几十 MB，背后的编码思路就从这棵树来：出现次数多的字符用短编码，出现少的用长编码，总体长度就下来了。
构造过程只有一步
记住一个动作：每次从集合里挑权值最小的两个节点，合并成一棵小树，新节点权值取两者之和，再放回集合，重复到只剩一棵树为止。
拿一组字符频率走一遍：a 是 45，b 是 13，c 是 12，d 是 16，e 是 9，f 是 5。先合并最小的 e(9) 和 f(5)，得 14；再合并 c(12) 和 b(13)，得 25；接着 14 和 16 合成 30；然后 25 和 30 合成 55；最后 45 和 55 合并，根节点权值 100。频率最低的 f 离根最远，频率最高的 a 离根最近，正好符合预期。
几个常考的硬性质
- n 个叶子的哈夫曼树一共 2n-1 个节点，而且没有度为 1 的节点
- 它是带权路径长度 WPL 最小的二叉树，WPL 等于每个叶子的权值乘以到根的路径长度再求和
- 同一组权值建出的树形态可能不唯一，但 WPL 一定相同
- 左右子树可以交换，编码里 0 和 1 怎么分配是人为约定的
和哈夫曼编码的关系
从根往下走，往左记 0，往右记 1，走到叶子就是该字符的编码。按上面的例子，a 的编码只有 1 位，其余字符在 3 到 4 位之间。任何一个编码都不是另一个的前缀，解码时从左到右扫不会歧义，这也是压缩文件能无差错还原的原因。解压端只需要树的形状，压缩文件头里一般存着频率表，解压时先重建树再逐位读。
动手实现注意什么
教材常用数组实现，n 个叶子开 2n-1 长度的数组，每次选最小要扫一遍，整体 O(n²)；数据量大了换小顶堆，取最小两个只要 O(log n)。用 C 语言写的时候，父指针和左右孩子指针都要存进结构体。调试时先拿两个节点试跑，把每次选中的权值打印出来，确认没选错再跑全量。
考试里判断一棵树是不是哈夫曼树，别看形状，直接算 WPL 比大小，谁最小谁是。