哈夫曼树

定义

带权路径最短的二叉树称为哈夫曼树或最优二叉树。

带权路径长度(WPL):设二叉树有n个叶子结点，每个叶子结点带有权值W(k), 从根结点到每个叶子结点的长度为l(K)，则每个叶子结点的带权路径长度之和就是： WPL = n西格玛K=1 w(k)l(k)

• 结构特点

  ：

  • 二叉树特例：严格来说是二叉树，但可扩展为多叉树（如 Huffman 编码中若要求码长为 n 进制，需构建 n 叉树）。
  • 带权路径长度最短的最优二叉树，叶子节点为字符及其权重。

• 分支数：默认二叉树（2 叉），扩展后可为多叉（如 3 叉、4 叉）。

• 典型应用

  ：

  • 数据压缩：如 JPEG 图像压缩、ZIP 格式的无损压缩，通过霍夫曼编码减少高频字符的存储位数。
  • 通信编码：在信道传输中优化数据传输速率，降低冗余（如电报码优化）。

哈夫曼树的构造

每次把权值最小的两颗二叉树合并

如：1 2 3 4 5

1和2合并值是3，

值3和结点3在合并值是6

4和5比值6小所以先构建4和5

4和5合并值是9，

值6和值9合并成值15

特点

1. 没有度为1的结点
2. n个叶子结点的哈夫曼树共有2n-1个结点 2.1 n0:叶结点总数 2.2 n1:只有一个儿子的结点总数 2.3 n2:有2个儿子的结点总数
3. 哈夫曼树的任意非叶子结点的左右子树交换后仍是哈夫曼树 对同一组权值{w1,w2,...,wn}，是否存在不同构的两颗哈夫曼树？可能

哈夫曼编码问题

怎么进行不等长编码？

如何避免二义性？

前缀码prefix code ：任何字符的编码都不是另一个字符的前缀

如： a:1 e:0 s:10 这个前缀码在上面出现所以有二义性

用二叉树用于编码

1. 左右分支：0、1
2. 字符只在叶结点上

当所有节点都在叶结点上的时候可以保证前缀码没有二义性