有关哈夫曼树和哈夫曼编码的一些问题和总结

*有关哈夫曼树和哈夫曼编码的一些问题和总结

一些简单的介绍：

1. 哈夫曼树又称为最优二叉树
2. 是一种带权路径最短的二叉树
   3.** 可以实现无损压缩和恢复（解压）**

带权路径

树的带权路径就是树中所有的叶节点的权值乘上其到根节点的路径长度，（若根节点为0，其叶节点到根节点的路径长度为叶结点的层数）

WPL = （ W1l1+W2L2+…+Wn*Ln）

注释：

树的带权路径长度(Weighted Path Length of Tree,简记为WPL)
　　1.结点的权：在一些应用中,赋予树中结点的一个有某种意义的实数.
　　2.结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积.
　　3.树的带权路径长度(Weighted Path Length of Tree)：定义为树中所有叶结点的带权路径长度之和,通常记为：WPL = （ W1l1+W2L2+…+Wn*Ln)
其中：
n表示叶子结点的数目
wi和li分别表示叶结点ki的权值和根到结点ki之间的路径长度.
树的带权路径长度亦称为树的代价.
3．最优二叉树或哈夫曼树
　在权为wl,w2,…,wn的n个叶子所构成的所有二叉树中,带权路径长度最小(即代价最小)的二叉树称为最优二叉树或哈夫曼树.

哈夫曼编码如何实现？

例：
A 15,B 10,C 40,D 30, E 5

**1.**按照权值的大小排序
即 E B A D C
并拿出最小的两个节点作为左右子树构成一个新的树 其根设为N1 并令N1的权值为两个叶子权值的和（即E 5 + B 10 = N1 15）
此时我们已经获得了N1的权值（15）。
**2.**将余下的节点包括N1继续排序
N1（15） A (15) D(30) C(40)
重复1的操作 即N1为左右子树 N2为他俩的根节点，权值为N1（15）+A(15) = N2(30)
**3.**重复操作，（直到全部完成，并将最后的全部树连接起来。

结果如下:

通过以上步骤 ，我们即可完成创建哈夫曼树，其中在构建哈夫曼树时，左零右一。

由此哈夫曼树，我们即可的到各个编码，
即
A：101；
B：1001；
…
我们常用的JPEG格式就是这种技术所实现的。

如果有任何疑问，欢迎评论，期待与大家的交流。

感谢阅读。
create By lazarus