霍夫曼树（图解霍夫曼编码）

　　霍夫曼树（图解霍夫曼编码）简明易懂的霍夫曼编码来啦，用图片的形式解答霍夫曼是不是很简单呢，浏览完本文就去动手试一试吧！
　　责编张红月
　　出处沉默王二
　　今天来给大家普及一下霍夫曼编码（HuffmanCoding），一种用于无损数据压缩的熵编码算法，由美国计算机科学家大卫霍夫曼在1952年提出这么专业的解释，不用问，来自维基百科了。
　　说实话，很早之前我就听说过霍夫曼编码，除了知道它通常用于GZIP、BZIP2、PKZIP这些常规的压缩格式中，我还知道它通常用于压缩重复率比较高的字符数据。
　　大家想啊，英文就26个字母进行的无限组合，重复率高得一逼啊！常用的汉字也不多，2500个左右，别问我怎么知道的，我有问过搜索引擎的。
　　字符重复的频率越高，霍夫曼编码的工作效率就越高！
　　是时候，和大家一起来了解一下霍夫曼编码的工作原理啦，毕竟一名优秀的程序员要能做到知其然知其所以然请允许我又用了一次这句快用臭了话。
　　假设下面的字符串要通过网络发送。
　　大家应该知道，每个字符占8个比特，上面这串字符总共有15个字符，所以一共要占用158120个比特。没有疑问吧？有疑问的同学请不好意思下。
　　如果我们使用霍夫曼编码的话，就可以将这串字符压缩到一个更小的尺寸。怎么做到的呢？
　　霍夫曼编码首先会使用字符的频率创建一棵树，然后通过这个树的结构为每个字符生成一个特定的编码，出现频率高的字符使用较短的编码，出现频率低的则使用较长的编码，这样就会使编码之后的字符串平均长度降低，从而达到数据无损压缩的目的。
　　拿上面这串初始字符来一步步的说明下霍夫曼编码的工作步骤。
　　计算字符串中每个字符的频率
　　B出现1次，C出现6次，A出现5次，D出现3次。
　　按照字符出现的频率进行排序，组成一个队列Q
　　出现频率最低的在前面，出现频率高的在后面。
　　把这些字符作为叶子节点开始构建一颗树
　　首先创建一个空节点z，将最小频率的字符分配给z的左侧，并将频率排在第二位的分配给z的右侧，然后将z赋值为两个字符频率的和。
　　B的频率最小，所以在左侧，然后是频率为3的D，在右侧；然后把它们的父节点的值设为4，子节点的频率之和。
　　然后从队列Q中删除B和D，并将它们的和添加到队列中，上图中表示的位置。紧接着，重新创建一个空的节点z，并将4作为左侧的节点，频率为5的A作为右侧的节点，4与5的和作为父节点。
　　继续按照之前的思路构建树，直到所有的字符都出现在树的节点中。