数据结构与算法_哈夫曼编码

举个构建哈夫曼树的例子：

1）选择没有双亲权值最小的两个结点，t1,t2;

2) t1,t2做为左右子树构建一颗新树；

3）新树的根为t1,t2之和；

哈夫曼树

采用顺序存储的方式：

1.首先初始化一个数组：其中 -1 表示数组的下标，-1表示不存在；

2.然后开始依次寻找两个最小的结点，构建新树，重新填表；

构建哈夫曼树其实就是填表，哈夫曼编码其实就是读表。

哈夫曼带权路径长度

WPL=每个叶子的权值*该叶子到根的路径长度之和

哈夫曼树带权路径长度之和=各新生成结点的权值之和，可以看作最终的编码长度。