【数据结构】哈夫曼编码与最优二叉树（哈夫曼树）
一.为什么要用哈夫曼编码
在进行大容量存储、图像压缩等数据交换的时候，如果文件过大，恰好WIFI又不怎么快，你是不是会觉得十分暴躁呀？比如有这样一串数据需要传输：
上面就有100位二进制数，这还只是数字，如果要传输英文字母、中文等需要更多的二进制位数：
这种完完整整原原本本地传输数据的方法叫固定长度压缩算法。
但是如果通过哈夫曼编码之后，就会变成数据+转换表（也就是非固定可变长度压缩算法，）：
只需要10+8+32= 50位！！节省了将近50位的数据！！
二.哈夫曼树
那么哈夫曼编码是怎么进行数据存储的呢？建立一个二叉树！！名字就叫哈夫曼树！！比如下面这个例子：
请将数据HELLO进行哈夫曼编码，第一步统计各个字母出现的频率：
然后再按照出现频率低往高进行编树，首先是出现频率最低的“H” 和 “E”和“O”（随便挑两个） ，因为是概率最低，所以作为最低的叶子节点：
两个权值（也就是频率）相加后，放入到频率中：
紧接着最低的是“0” 出现频率为“ 1”，和另外两个同样权值的，那就随便选择其中一个 ：
最后只剩下两个权值：
将两个子树接在一起：
随后，将左子树的路径都赋值为“0”，右子树为“1”：
如此，一颗哈夫曼树就这样被构造出来了！！可以观察到，我们的叶子节点全部都是需要传输的数据。所以HELLO通过哈夫曼编码后就会变成：
一共占据50位。
综合以上内容，可以总结以下知识点：
- 需要传输的数据都是作为叶子节点存在的
- 按照频率从低到高进行排序
- 再满足哈夫曼树的基础上，尽量让二叉树满足平衡二叉树的结构，使得数据更加简洁地进行排序，相关平衡二叉树可以查看：【数据结构】十分钟透彻了解各种二叉树的基础概念