哈夫曼树

1. 定义

节点的路径长度：从根节点到该节点的路径上的连接数。

树的路径长度：树的叶子节点的路径长度之和。

节点带权路径长度：节点的路径长度与节点的权值的乘积。

树的带权路径长度：WPL(Weighted Path Length)是树中所有叶子节点的带权路径长度之和。

定义：给定n个权值作为n个叶子节点，构造一棵二叉树，若这棵二叉树的带权路径长度达到最小，则称这样的二叉树为最优二叉树，也称为Huffman树。

2. 构建哈夫曼树

**WPL的值越小，构造出来的二叉树的性能越优。**如何构造最优二叉树(哈夫曼树)，步骤如下：

• 重复以下步骤：
  • 按照节点的权值对节点排序；
  • 拿出权值最小的两个节点作为生成新的节点的左右子树，新生成节点权重为拿出的两个节点权重的和。
• 直到只剩最后的根节点。

示例：A-8, D-1, E-4, F-1, R-5, T-3

3. 哈夫曼编码与C语言实现

编码：

1. 对元素进行权值排序；

2. 用代码构建一个哈夫曼树(最优二叉树)；

3. 以左子树路径记为0右子树为1，从根节点到每个元素(叶子节点)的路径作为该元素的编码，用table记录元素与其编码的对应关系；

4. encoder：遍历要编码的文本或文件中的元素，对应table中元素的编码，输出encode后的文本或文件编码。

5. decoder：从编码中取出0或1，从根节点开始，根据编码值向左子树或右子树遍历，直到到达叶子节点，即为这段编码对应的元素。重复以上过程直到全部解码结束。

   注：构建的哈夫曼树，由于每一个元素都是叶子节点，左子树路径为1右子树路径为0，以从根节点到该叶子节点的路径编码，这样，到达叶子节点形成的编码刚好是一种前缀编码，即没有任何一个节点的编码是其他编码的前缀(即开头)，因为任何一个我们编码的节点都是叶子节点，即没有孩子了，所以路径到这里就断了，也就没有以当前节点路径(编码)为前缀路径(编码)的节点了。这样，虽然每个元素的编码位数不同，编码后的所有元素的编码连在一起如00101101110101…，即使不用上面遍历二叉树的方法，我们也能通过查table表的方法轻易解码，就是凭借前述前缀编码的特点：没有任何一个节点的编码是其他编码的前缀(即开头)。

实现：代码见【D:\01_Learning\数据结构\数据结构和算法_小甲鱼\第五十三讲赫夫曼编码C语言实现\huffman】

参考：小甲鱼的数据结构