设二叉树具有 $n$ 个带权叶结点，从根结点到各叶结点的路径长度与相应叶节点权值的乘积之和称为树的带权路径长度（Weighted Path Length of Tree, WPL）。 —— 引用自 OI Wiki
设第 $i$ 个叶节点权值为 $w_i$，根节点到其路径长度为 $l_i$，则 WPL 计算为
$$ \sum_{i=1}^nw_il_i $$
该二叉树的 WPL 值为 2 * 2 + 3 * 2 + 4 * 2 + 7 * 2 = 32.
给定一组带权叶节点，构造出的 WPL 值最小的二叉树称为哈夫曼树。其中，叶节点权值越大，离根越近；权值越小，离根越远。
哈夫曼算法用于构建哈夫曼树。
初始将 $n$ 个叶节点建为只有根节点的二叉树，随后选取根节点权值最小的两棵树，合并为新的二叉树，其新的根节点是这两棵树的根节点权值之和。不断重复这一合并过程直到剩余一棵二叉树，这棵二叉树就是哈夫曼树。
下图展示了构建过程。
在进行程序设计时，通常给每一个字符标记一个单独的代码来表示一组字符，即 编码。
在进行二进制编码时，假设所有的代码都等长，那么表示 $n$ 个不同的字符需要 $\lceil\log_2n\rceil$位，称为等长编码。
如果每个字符的使用频率相等，那么等长编码无疑是空间效率最高的编码方法，而如果字符出现的频率不同，则可以让频率高的字符采用尽可能短的编码，频率低的字符采用尽可能长的编码，来构造出一种不等长编码，从而获得更好的空间效率。
在设计不等长编码时，要考虑解码的唯一性，如果一组编码中任一编码都不是其他任何一个编码的前缀，那么称这组编码为前缀编码，其保证了编码被解码时的唯一性。
哈夫曼树可用于构造最短的前缀编码，即哈夫曼编码（Huffman Code）。
—— 引用自 OI Wiki
假设现在有字符集 $d_1,\dots,d_n$，其出现频率为 $w_1,\dots,w_n$，需要对其构造哈夫曼编码。我们利用哈夫曼算法，将 $d_1,\dots,d_n$ 作为叶节点，频率作为权值，构造一棵哈夫曼树。构造完成后，规定左分支代表 $0$，右分支为 $1$，那么由根节点到每个字符 $d_i$ 的路径就是其对应的二进制编码。
