哈夫曼编码、哈夫曼树

        已知一个文件中出现的各字符及其对应的率如下表所示。若采用定长编码，则该文件中字符的码长应为( )。若采用Huffman编码，则字符序列face的编码应为（ )

        码长决定了可以显示几位字符，题中一共有6位，那么就应该是2 ^ 3 , 码长至少为3位。

       得出哈夫曼编码分为两步：

一、绘制哈夫曼树（哈夫曼树叫做带权最短路径树）

        首先获取两个最小的值（9,5）添加到树中，左边为较小的值，右边为较大的值。将两值相加得到新的节点 14

        再获取两个最小的值（13,12） 与新的节点作比较，发现13 和 12 都小于 新节点14，那就再画一个树，并获取新的节点 25

         两个树的排序位置也要遵循小的在左，大的在右。然后再次获取最小的两个值（45,16），然后发现 16大于14 而小于25，那么16和14组成新的树。生成新的节点 30

         最后只剩下45了，而45大于25，大于30，那么它只能作为单独一个节点加入到树中（哈夫曼树是二叉树的一种，最多能有左子树和右子树），将25和30相连生成新的节点55。

        到这第一步就完成了，生成了哈夫曼树。

第二步、生成哈夫曼编码

        在哈夫曼树中左子树标记为0，右子树为1

                将字符填入对应的结点中

         最后得出节点对应的编码：a:0 , b:101 , c:100, d: 111,e:1101, f : 1100

         face的编码应为（1100 0 100 1101 )