第1个回答 2022-06-05
首先先来看四个和树相关的概念：
如上图所示，二叉树 a 中，结点 A 到结点 B 之间的路径长度为3，树的路径长度为1+1+2+2+3+3+4+4=20，树的带权路径长度为 5*1+15*2+40*3+30*4+10*4=315 。二叉树 b 中，结点 A 到结点 B 之间的路径长度为2，树的路径长度为1+2+2+3+3+1+2+2=16，树的带权路径长度为 5*3+15*3+40*2+30*2+10*2=220 。
计算我们构造的新二叉树的 WPL 为 40+30*2+15*3+4*5+4*10=205 ，比二叉树 b 还要小15。
图中红色字的结点即为原来的结点，黑色字的结点是新生成的结点。总结步骤如下：
哈夫曼树被发明出来的主要目的是解决当年远距离通信的数据传输最优化的问题。比如需传送的电报为 BADCADFEED ，它只用到6种字符，我们可以使用对应的二进制数来进行表示：
传输后的编码就是 001 000 011 010 000 011 101 100 100 011 。这种等长的编码虽然使用起来方便，但是编码结果太长，会占用过多的内存资源。如果我们对上述字母进制做一些修改：
此时，新生成的编码 001 01 00 101 01 00 1001 11 11 00 就比等长编码短了，节约了存储和传输成本。但是这种方式也有缺陷，比如一个字符的编码恰好是另一个字符编码的前缀，就会产生歧义。这时，哈夫曼编码 (Huffman Coding) 就登场了。它实现了两个重要的目标：
哈夫曼编码不是一套固定的编码，而是通过哈夫曼树，根据给定信息中各个字符出现的频次，动态生成最优的编码。假设需要编码的字符集为{ }，每个字符出现的次数为{ }，我们以 为叶子结点，以 为对应叶子结点的权值来构造一棵哈夫曼树，规定左分支为0，右分支为1，则从根结点到叶子结点所经过的路径分支组成的0和1的序列即为该结点的字符编码，这个编码就是哈夫曼编码。
下面我们就使用顺序存储结构来实现哈夫曼树及哈夫曼编码。由于结点存在权值，且我们使用的是顺序存储结构，可以通过下标来获取到左右孩子、双亲结点。
个叶子结点的二叉树会有 个结点，构建哈夫曼树的时候，由于我们使用的是顺序存储结构，我们可以将叶子结点存放在前 个位置，而非叶子结点，存放在后面，使用下标来标记。
生成哈夫曼编码时候，左孩子的编码记为0，右孩子的编码记为1。编码结构中首先要保存的是编码，由于编码可能存在多位，我们需要把读到第几位记录下来，另外还需要保存该字符的权值。
验证如下：