Huffman Tree

定义

哈夫曼树（Huffman Tree）是一种带权路径长度最短的二叉树，又称最优二叉树，常用于数据压缩编码。

带权路径长度 WPL

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

其中 $w_i$ 为第 $i$ 个叶子结点的权值，$l_i$ 为该叶子结点到根的路径长度。

构造方法

1. 将 n 个权值作为 n 棵只有根结点的二叉树，构成森林
2. 每次选取两棵根结点权值最小的树合并，新根权值为两者之和
3. 重复步骤 2，直到只剩一棵树

哈夫曼编码

• 固定长度编码：每个字符编码长度相同
• 可变长度编码：高频字符用短编码，低频字符用长编码
• 前缀编码：任一编码都不是其他编码的前缀，保证解码唯一性

哈夫曼编码是一种最优前缀编码。