树和二叉树的应用 -- ---哈夫曼（Huffman）树和哈夫曼编码

1、哈夫曼树的定义

    》》 在许多应用中，树中结点常常被赋予一个表示某种意义的数值，称为该结点的权。从树根结点到

           任意结点的路径长度（经过的边数 ） 与该结点上权值的乘积称为该结点的带权路径长度。

    》》 树中所有叶结点的带权路径长度之和称为该树的带权路径长度，记为：

               WPL = 

          其中  是第 i 个叶结点所带的权值；  是该叶结点到根结点的路径长度。

     》》 在含有 N 个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为“ 哈夫曼树 ”，

          也称为 “ 最优二叉树 ”。

     》》 案例： 下面的案例中有 3 棵二叉树，都有 4 个叶子结点 a 、 b 、 c 、 d ，分别带权 7 、 5 、 2 、 4 ，

            它们的带权路径长度分别为：

            

            

                   

                （a） WPL = 7*2+5*2+2*2+4*2 = 36

                （b）WPL =  7*3+5*3+2*1+4*2 = 46

                （c） WPL = 7*1+5*2+2*3+4*3 = 35

                  通过计算 WPL ， 可得知（c） 树中的 WPL 最小，验证，它恰为“ 哈夫曼树 ”

2、哈夫曼树的构造

       》》 给定 N 个权值分别为 W1 , W2 ,W3 , ... , Wn  的结点。通过哈夫曼算法可以构造出最优二叉树，

             算法的描述如下：

                1）、将这个 N 个结点分为作为 N 棵仅含有一个结点的二叉树，构成森林 F 。

                2）、构造一个新结点，并从 F 中选取两棵根结点权值最小的树作为新结点的左、右子树，

                       并且将新结点的权值置为左、右子树上根结点的权值之和。

                 3）、从 F 中删除刚才选出的两棵树，同时将新得到的树加入 F 中 。

                 4）、重复步骤 2）、3） ，直至 F 中只剩下一棵树为止。

               补充： 从上述构造过程中可以看出哈夫曼树具有如下特点

                  1）、每个初始结点最终都成为叶结点，并且权值越小的结点到根结点的路径长度越大。

                  2）、构造过程中总共新建了 N -1 个结点（双分支结点），因此哈夫曼树中结点总数为

                            2N -1 。

                  3）、每次构造都选择了2 棵树作为新结点的孩子，因此哈夫曼树中不存在度为 1 的结点。

3、哈夫曼编码

       》》 对于待处理的一个字符串序列，如果对每个字符用同样长度的二进制位来表示，则称这种编码

            方式为“ 固定长度编码 ”。

               若允许对不同字符用不等长的二进制位表示，则这种方式称为“ 可变长度编码 ”。

        》》 可变长度编码比固定长度编码好得多，其特点是对频率高的字符赋以短编码，而对频率较低的

              字符赋以较长一些的编码，从而可以使字符串平均编码长度减短，起到压缩数据的效果。

                  哈夫曼编码是一种被广泛应用而且非常有效的数据压缩编码。

         》》 如果没有一个编码是另一个编码的前缀，则称这样的编码为“ 前缀编码 ” 。 如 0 、 101 、100 是

              前缀编码。对前缀编码的解码也是很简单的，因为没有一个码是其他码的前缀。所以，可以识别出

              第一个编码，将它翻译为原码，再对余下的编码文件重复同样的操作。如 00101100 可被唯一地分

              析为 0 、 0 、 101 、 100。