【数据结构】哈夫曼编码与最优二叉树（哈夫曼树）

一.为什么要用哈夫曼编码

        在进行大容量存储、图像压缩等数据交换的时候，如果文件过大，恰好WIFI又不怎么快，你是不是会觉得十分暴躁呀？比如有这样一串数据需要传输：

         上面就有100位二进制数，这还只是数字，如果要传输英文字母、中文等需要更多的二进制位数：

        这种完完整整原原本本地传输数据的方法叫固定长度压缩算法。

        但是如果通过哈夫曼编码之后，就会变成数据+转换表（也就是非固定可变长度压缩算法，）：

        只需要10+8+32= 50位！！节省了将近50位的数据！！

二.哈夫曼树

        那么哈夫曼编码是怎么进行数据存储的呢？建立一个二叉树！！名字就叫哈夫曼树！！比如下面这个例子：

        请将数据HELLO进行哈夫曼编码，第一步统计各个字母出现的频率：

​​​​​​​   

       然后再按照出现频率低往高进行编树，首先是出现频率最低的“H” 和 “E”和“O”（随便挑两个） ，因为是概率最低，所以作为最低的叶子节点：

        ​​​​​​​ 

        两个权值（也就是频率）相加后，放入到频率中：

         

        紧接着最低的是“0” 出现频率为“ 1”，和另外两个同样权值的，那就随便选择其中一个 ：

        ​​​​​​​

        最后只剩下两个权值：

        

        将两个子树接在一起：

         

         随后，将左子树的路径都赋值为“0”，右子树为“1”：

        

         如此，一颗哈夫曼树就这样被构造出来了！！可以观察到，我们的叶子节点全部都是需要传输的数据。所以HELLO通过哈夫曼编码后就会变成：

        一共占据50位。

        综合以上内容，可以总结以下知识点：

• 需要传输的数据都是作为叶子节点存在的
• 按照频率从低到高进行排序
• 再满足哈夫曼树的基础上，尽量让二叉树满足平衡二叉树的结构，使得数据更加简洁地进行排序，相关平衡二叉树可以查看：【数据结构】十分钟透彻了解各种二叉树的基础概念​​​​​​​