3.2用线性链表递归建立哈夫曼树

哈夫曼编码是基于哈夫曼树实现的一种编码方式，所以在实现哈夫曼编码压缩算法时，如何高效的建立哈夫曼树，是算法的首要任务。哈夫曼树的构造步骤如下[2]：

（1）根据给定的n个权值w1,w2,…,wn构成n棵二叉树的森林F={T1,T2,…,Tn}，其中每一棵二叉树Ti中都只有一个权为wi的根结点，其左、右子树为空。

（2）在森林F中选出两棵根结点权值最小的树作为一棵新二叉树的左、右子树，新二叉树的根结点的权值为其左、右子树根结点的权值之和。

（3）从F中删掉这两棵二叉树，同时把新二叉树加入到F中。

（4）重复步骤（2）、（3），直到F中只含有一颗树为止，此树便为最优二叉树（哈夫曼树）。

通过分析哈夫曼树的构造过程，每次要取出森林中根结点权值最小的两棵二叉树，再将新二叉树插入到森林中。这个过程涉及到对森林F这个数据结构的插入、删除以及排序。考虑到链表这一数据结构的删除、插入操作的高效性，以及线性链表的有序性。所以笔者用线性链表来实现森林这一数据结构。

3.3通过递归时形参的传递进行编码

传统的哈夫曼编码采取从叶子结点往上编码，编码结束后，需要将编码反序，得到最终的哈夫曼编码，算法的时间复杂度为O(n2)。从叶子结点向上编码，当两片或多片叶子节点的路径出现部分重合时，算法会有一部分冗余的计算。如图2-1，以A，B两个叶子结点为例，当我们在计算它们的哈夫曼编码时，R3～R1这段路程被重复的计算了两次。而如果从根结点向下编码，则不会出现重复的路程，如图2所示，以先序为例，箭头旁边的数字代表遍历的顺序。故从根结点向下编码在效率上高于从叶子结点向上编码。