《数据结构与算法》总结（七）哈夫曼树

目录

• 哈夫曼编码（Huffman Coding）
• 哈夫曼树
• 构建哈夫曼树
• 构建哈夫曼编码

一 哈夫曼编码（Huffman Coding）

哈夫曼编码，又称为霍夫曼编码，它是现代压缩算法的基础

假设要把字符串【ABBBCCCCCCCCDDDDDDEE】转成二进制编码进行传输

• 可以转成ASCII编码(65_69，10000011000101)，但是有点冗长，如果希望编码更短呢?

• 可以先约定5个字母对应的二进制

A	B	C	D	E
000	001	010	011	100

对应的二进制编码:

000001001001010010010010010010010010011011011011011011100100 

一共20个字母，转成了60个二进制位

如果使用哈夫曼编码，可以压缩至41个二进制位，约为原来长度的68.3%

二 哈夫曼树

先计算出每个字母的出现频率(权值，这里直接用出现次数)，【ABBBCCCCCCCCDDDDDDEE】

A	B	C	D	E
1	3	8	6	2

利用这些权值，构建一棵哈夫曼树(又称为霍夫曼树、最优二叉树)

如何构建一棵哈夫曼树?(假设有 n 个权值)

1. 以权值作为根节点构建n棵二叉树，组成森林
2. 在森林中选出2个根节点最小的树合并，作为一棵新树的左右子树，且新树的根节点为其左右子树根节点之和
3. 从森林中删除刚才选取的2棵树，并将新树加入森林
4. 重复2、3步骤，直到森林只剩一棵树为止，该树即为哈夫曼树

三 构建哈夫曼树

image

四 构建哈夫曼编码

image

left为0，right为1，可以得出5个字母对应的哈夫曼编码

A	B	C	D	E
1110	110	0	10	1111

【ABBBCCCCCCCCDDDDDDEE】的哈夫曼编码是

image

总结

• n 个权值构建出来的哈夫曼树拥有 n 个叶子节点
• 每个哈夫曼编码都不是另一个哈夫曼编码的前缀
• 哈夫曼树是带权路径长度最短的树，权值较大的节点离根节点较近
• 带权路径长度:树中所有的叶子节点的权值乘上其到根节点的路径 长度。与最终的哈夫曼编码总长度成正比关系。

---

作为一个开发者，有一个学习的氛围跟一个交流圈子特别重要，这是一个我的iOS交流群：413038000，不管你是大牛还是小白都欢迎入驻 ，分享BAT,阿里面试题、面试经验，讨论技术， 大家一起交流学习成长！

以下资料在群文件可自行下载！

推荐阅读

iOS开发——最新 BAT面试题合集（持续更新中）

作者：路飞_Luck
链接：https://www.jianshu.com/p/76c1cc1dca7e
来源：简书