[转载]Huffman树

1. 定义

huffman编码是一种可变长编码方式，依据字符在需要编码文件中出现的概率提供对字符的唯一编码，并且保证了可变编码的平均编码最短，被称为最优二叉树，有时又称为最佳编码。

2.概念

1. 树的路径长度：根节点到每一个节点的路径长度为 i
2. 节点的带权路径长度：节点到根节点之间的路径长度 i 与节点权重 w 的乘积
3. 树的带权路径长度：所有节点的带权路径长度之和

若干个节点，每一个节点的权重为w1，w2，w3，..,Wn，这n个节点为叶子节点，构造一个有n个叶子节点的二叉树，具有最短的带权路径长度的二叉树为huffman树。

• 图3 的带权路径长度最短，就是Huffman树

3. Huffman编码

• 编码结果： a：0 ，b：10， c：110，d：111
• 注意 a、b、c、d都必须是叶子节点

4. 如何构建Huffman数以及Huffman编码

构造huffman树的哈夫曼算法如下：
（1）n节点的权值｛w1、w2、·····，wn｝构成n棵二叉树集合F=｛T1，T2，···，Tn｝，每棵二叉树Ti只有一个带权为Wi的根节点，左右孩子均空。
（2）在F中选取两棵根节点权值最小的作为树的左右孩子构造一棵新的二叉树，且置根节点的权值为左右孩子权值之和，在F中删除这两棵树，新二叉树之于F中
（3）重复（2），直到F中只有一棵树为止，这棵树就是huffman树。