数据结构之哈弗曼树与哈弗曼编码

一.哈弗曼树和哈弗曼编码先知
哈弗曼树是二叉树中一种特殊的树，也被称为最优二叉树。其通过某种规则（权值）来构造出一哈夫曼二叉树，在这个二叉树中，只有叶子节点才是有效的数据节点，其他的非叶子节点是为了构造出哈夫曼而引入的！

哈夫曼编码是通过哈夫曼树进行的一种编码，一般情况下，以字符‘0’与‘1’表示。编码的实现过程很简单，只要实现哈夫曼树，通过遍历哈夫曼树，规定向左子树遍历一个节点编码为“0”，向右子树遍历一个节点编码为“1”，结束条件就是遍历到叶子节点！因为上面说过：哈夫曼树叶子节点才是有效数据节点！
二.构造哈弗曼树
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：

(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；

(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

(3)从森林中删除选取的两棵树，并将新树加入森林；

(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

例子：
我们用图画来构造一颗哈弗曼树


注意：为了使得到的哈夫曼树的结构尽量唯一，通常规定生成的哈夫曼树中每个结点的左子树根结点的权小于等于右子树根结点的权。
三.哈弗曼编码
哈夫曼编码使用一种特别的方法为信号源中的每个符号设定二进制码。出现频率更大的符号将获得更短的比特，出现频率更小的符号将被分配更长的比特，以此来提高数据压缩率，提高传输效率。具体编码步骤主要为，

　　1、统计：

　　在开始编码时，通常都需要对信号源，也就是本文的一段文字，进行处理，计算出每个符号出现的频率，得到信号源的基本情况。接下来就是对统计信息进行处理了

　　2、构造优先对列：

　　把得到的符号添加到优先队列中，此优先队列的进出逻辑是频率低的先出，因此在设计优先队列时需要如此设计，如果不熟悉优先队列，请阅读相关书籍，在此不做过多概述。得到包含所有字符的优先队列后，就是处理优先队列中的数据了。

　　3、构造哈夫曼树：

　　哈夫曼树是带权值得二叉树，我们使用的哈夫曼树的权值自然就是符号的频率了，我们构建哈夫曼树是自底向上的，先构建叶子节点，然后逐步向上，最终完成整颗树。先把队列中的一个符号出列，也就是最小频率的符号，，然后再出列一个符号。这两个符号将作为哈夫曼树的节点，而且这两个节点将作为新节点，也就是它们父节点，的左右孩子节点。新节点的频率，即权值，为孩子节点的和。把这个新节点添加到队列中(队列会重新根据权值排序)。重复上面的步骤，两个符号出列，构造新的父节点，入列……直到队列最后只剩下一个节点，这个节点也就是哈夫曼树的根节点了。

　　4、为哈弗曼树编码：

　　哈夫曼树的来自信号源的符号都是叶子节点，需要知道下。树的根节点分配比特0，左子树分配0，右字数分配1。然后就可以得到符号的码值了。
　　例如上边的例子：
　　
　　这样各个字符对应的编码分别为：
　　A——011
　　B——00001
　　C——1
　　D——00000
　　E——001
　　F——010
　　G——0001
　　四.参考文献
　　http://blog.sina.com.cn/s/blog_50d705670101k0hk.html
　　https://www.cnblogs.com/junyuhuang/p/4127095.html