【数据结构】哈夫曼树和哈夫曼编码

给定一个序列，将序列中的所有元素作为叶子节点构建一棵二叉树，并使这棵树的带权路径长度最小，那么我们就得到了一棵哈夫曼树（又称最优二叉树）

接下来是名词解释：

例如下面这棵哈夫曼树：

通过观察我们可以发现，所有父节点的权值都是自身的两个子节点的权值之和。而为了要使树的带权路径长度最小，我们要尽可能的让权值小的节点离根节点远，让权值大的节点离根节点近。

因此，我们引出哈夫曼树的构造算法。

要将一个序列构造成一棵哈夫曼树，我们首先需要对其进行升序排序

将排序好后的序列中的每个值看作一棵只有一个节点的树，从中选出根节点权值最小的两棵树作为新树的左右子树，并将这两棵树从序列中删除，而新树的根节点的权值是这两棵树根节点的权值之和

哈夫曼树没有规定左右子树的顺序，因此下面的例子中将10和18的位置对调也是正确的

将新树的根节点的权值放入序列中并重新进行升序排序，重复上述步骤

至此，就构建了一棵哈夫曼树

因为哈夫曼树没有规定左右子树的顺序，因此一个序列可以构建出不同的哈夫曼树

假设我们要对一个字符串ABAACDC进行二进制编码

我们可以按顺序给每个字符设置一个编码，A为0，B为1，C为10，D为11

那么就可以将上面的字符串转化为0100101110

但是在解码的时候我们会发现，这一串二进制序列可以解码为ACACDBA、ACABABDA等字符串，出现了歧义。

这是因为我们在对字符进行编码的时候，出现了一个字符是另一个字符的前缀的情况，例如D可以用两个B来表示。

为了避免歧义，我们可以采用等长编码的方案，就是每个字符的编码都一样长，例如A为00，B为01，C为10，D为11，这样就不会产生歧义了。

但是这种方案并不是一个最短的方案。

统计字符出现的次数，把字符定义成一个节点，节点的权值就是它出现的次数。

例如上面A出现了3次，B出现了1次，C出现了2次，D出现了1次

哈夫曼编码的核心思想就是让出现次数越多的字符编出来的码越短，我们将全部节点构建成一棵哈夫曼树，出现次数越少的字符对应的节点就越靠近树的底层，编码也就越长，出现次数越多的字符编码就越短。

对二叉树的边标号，向左的边标为0，向右的边标为1，至此所有字符的编码就是从根节点到该字符节点路径上经过的标号，例如A为1，B为010，C为00，D为011，这种编码方案就叫做哈夫曼编码。

构建哈夫曼树的时候，所有的字符节点都是叶子节点，不会出现一个字符出现在另一个字符的路径上，也就不会出现一个字符是另一个字符的前缀这种造成歧义的情况

哈夫曼树的编码不是唯一的，节点放置的左右也会造成字符编码的不同，但是生成的编码长度一定都是一样的。

完.