Question

求解，关于数据结构的哈夫曼编码的问题

在此题中，方案1的WPL是怎么求得的？那里的2、4、5是怎么来的？而方案2的WPL又是怎么求得 那里 3（……）=的3是怎么来的？下面在写的逻辑结构哈夫曼编码的0010、10、00000……是怎么求来的？尤其下面的图，圆圈里的数字是怎么求得的？而线上的0、1又怎么得来？？？

Answer 1

方案一应该指的就是下面那个图了.
下面那个图是一棵二进制的哈夫曼树,其中因为是二进制编码,所以使用的是0\1的边.
那么对于每一个叶子节点来说,从根节点到叶子节点走过的边就是这个数字的编码.

那么举一个例子,比如频数=2的也就是最左端的那个叶节点,根到它走了5个0,它的编号就是"00000";在比如说10这个叶子节点,根节点到他走了"0011",它的编号也就是0011.
那么根据上面几个例子,那么叶子到根的距离[叶子的深度],也就是边的条数,就是这个叶子所代表的编码长度.
比如19\32\21到根的距离都是2,7\6\10到根的距离都是4,2\3到根的距离都是5.
也就是上面那个WPL的系数的意思.
表示单个编码长度*使用频率=总的编码长度.

而方案二表示的传统编码,就是上面表格中的那个等长编码:"000""001"...
它们的长度都是3,所以就是*3

然后为什么哈夫曼编码正确而且最优呢?

哈夫曼编码由于构成了一棵树,而且是叶子节点作为编码的代表,所以没有任何一个编码是另一个编码的前缀,所以哈夫曼编码是一个具有正确性的编码.
然后哈夫曼树的构造是根据贪心的思想,每次选出两个最小的点合成一个新的点所构成的.就满足了最优性.
构造的过程应该书上会有写.我就不再赘述了.

Answer 2