@[toc]

本篇文章将讲述哈夫曼树的相关内容。

举个栗子

既然要学哈夫曼树，我们就得知道什么是哈夫曼树，哈夫曼树的作用是什么。我以一个例子来告诉大家哈夫曼树的概念和作用。

期末考试结束了，各个学校都在准备评定大家的考试成绩，现在有一个需求，将学生的百分制成绩转换为五分制成绩：

90 ~ 100：A
80 ~ 89：B
70 ~ 79：C
60 ~ 69：D
< 60：E

相信这个需求难不倒大家：

if(score < 60)
    grade = 'E';
else if(score < 70)
    grade = 'D';
else if(score < 80)
    grade = 'C';
else if(score < 90)
    grade = 'B';
else
    grade = 'A';

我们可以将该判断过程转化为一棵二叉树：
在这里插入图片描述
这样用于描述判断过程的二叉树，我们称其为判断树。

不过这样的判断过程是有缺陷的，比如我将各个分数段的人数比例列举出来：

90 ~ 100：10%
80 ~ 89：30%
70 ~ 79：40%
60 ~ 69：15%
< 60：5%

假设需要统计的学生人数为10000人，则对于小于60分的同学来说，它们只需要比较一次即得出结果，总共比较10000 * 5% = 500(次)。

对于60~69分的同学，它们的成绩需要比较两次才能得出结果，总共比较10000 * 15% * 2 = 3000(次)。

对于70~79分的同学，它们的成绩需要比较三次才能得出结果，总共比较10000 * 40% * 3 = 12000(次)。

对于80~89分的同学，它们的成绩需要比较四次才能得出结果，总共比较10000 * 30% * 4 = 12000(次)。

对于90~100分的同学，它们的成绩需要仍然需要比较四次才能得出结果，总共比较10000 * 10% * 4 = 4000(次)。

总共需要比较的次数为500 + 3000 + 12000 + 12000 + 4000 = 31500(次)。

其实我们对这棵判定树稍作修改就能减少一些不必要的比较，比如我将其改为如下图：
在这里插入图片描述
再来计算一下比较次数：
$$10000(3 * 20\% + 2 * 80\%) = 22000(次)$$

很显然，这两棵判断树的结构不一定，其比较次数不同，效率也就不一样。

那怎样才能找到比较次数最少的那棵判断树呢？
这就是哈夫曼树的作用，这棵最优的二叉树就是哈夫曼树。

哈夫曼树的基本术语

知道了什么是哈夫曼树之后，我们需要了解一下哈夫曼树中用到的一些基本术语。

路径

从树中的一个结点到另一个结点之间的分支构成两个结点间的路径。

两结点间路径上的分支数称为结点的路径长度。

比如下面的一棵二叉树：
在这里插入图片描述
则从结点A到结点B的路径长度为1，它们之间仅有一条分支数。

从结点A到结点D的路径长度为2，它们之间有两条分支数。

从结点D到结点G的路径长度为3，它们之间有三条分支数。

树的路径长度

从树的根结点到每个结点的路径长度之和。

所以刚才的二叉树的路径长度为：
$$1 + 1 + 2 + 2 + 3 + 3 = 12$$

在结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树，但是路径长度最短的不一定是完全二叉树。

权

将树种结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。

结点的带权路径长度

从根结点到该结点之间的路径长度与该结点的权的乘积。

比如还是这棵二叉树：
在这里插入图片描述
每个结点都给了相应的权值，则结点B的带权路径长度为：
$$5 * 1 = 5$$
结点D的带权路径长度为：
$$4 * 2 = 8$$
结点F的带权路径长度为：
$$1 * 3 = 3$$

树的带权路径长度

树中所有叶子结点的带权路径长度之和。

比如这样的一棵二叉树：
在这里插入图片描述
其树的带权路径长度怎么计算呢？
先求出每个叶子结点的带权路径长度，再累加即可：
$$WPL = 2 * 1 + 2 * 3 + 2 * 5 + 2 * 7 = 32$$

再看一棵二叉树：
在这里插入图片描述
该树的带权路径长度为：
$$WPL = 1 * 1 + 2 * 3 + 3 * 7 + 3 * 5 = 43$$

可以发现，同样数量的结点生成的二叉树，其树的带权路径长度不一样。

由此引出哈夫曼树的最终概念，哈夫曼树是带权路径长度最短的树。

需要注意的是，"带权路径长度最短"是在"度相同"的树中比较得出的结果，如果没有这个前提，就没有比较的意义，也就没有哈夫曼树的说法了。

所以最优二叉树说的就是带权路径长度最短的二叉树。

由上面的结论我们可以总结出以下规律：

权越大的叶子离根越近，树的带权路径长度越短
满二叉树不一定是哈夫曼树
具有相同带权结点的哈夫曼树不唯一

构造哈夫曼树

我们知道，权越大的叶子离根越近，树的带权路径长度越小，最终找到带权路径最小的那棵树，它就是哈夫曼树。

所以我们在构造哈夫曼树的时候，优先分配权值小的结点，这样就可以把权值大的结点留在后面，让其离根最近。这也是贪心算法的核心思想，即：总是做出在当前看来最好的选择。

下面具体介绍构造哈夫曼树的步骤：
首先，根据n个给定的权值{w₁，w₂，...，w_n}构成n棵二叉树的森林，F = {T₁，T₂，...，T_n}，其中T_i只有一个带权为w_i的根结点。

然后在F中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且设置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。

接着在F中删除这两棵树，同时将新得到的二叉树加入到森林中。

重复这些步骤，直到森林中只剩下一棵树为止，这棵树即为哈夫曼树。

上述步骤可以总结为以下口诀：

构造森林全是根
选用两小造新树
删除两小添新人
重复2、3剩单根

光讲理论肯定有很多同学不理解，下面我举一个例子：
假设有四个结点A、B、C、D，权值分别为7，5，2，4，请构造哈夫曼树。

我们先进行第一步，构造森林全是根.现在有四个叶子结点，所以我们需要构造四棵树：
在这里插入图片描述
然后是第二步，选用两小造新树。这里两棵权值最小的树为C和D。

根据两棵权值最小的树造一棵新树，即在两个结点上方添加一个根结点，权值为左右孩子的权值之和。

第三步，删除两小添新人。在森林中把权值最小的两棵树删除掉，然后把新产生的树添加到森林中。
在这里插入图片描述
接下来就是重复步骤了，继续从森林中找出权值最小的两棵树，现在为树B和新生成的树。
我们仍然用这两棵树生成一棵新树：

然后在森林中删除这两棵树，把新生成的树添加到森林：

最后，将树A和树B生成一棵新树：
在这里插入图片描述
这样哈夫曼树就构造完成了。

由构造过程也可以得出如下结论：

哈夫曼树的结点的度只可能为0或2，没有度为1的结点
包含n棵树的森林要经过n - 1次合并才能形成哈夫曼树，共产生n - 1个新结点
包含n个叶子结点的哈夫曼树中共有2n - 1个结点

构造哈夫曼树算法实现

上面介绍了如何构造哈夫曼树，接下来需要关心的就是整个构造过程该如何用代码来实现呢？

这里采用顺序存储结构，使用一维结构数组来实现，先来定义结点类型：

typedef struct {
   
   
    int weight;        //权值
    int parent,lch,rch;
}HTNode,*HuffmanTree;

接下来是算法实现：

//构造哈夫曼树
void CreateHuffmanTree(HuffmanTree HT,int n){
   
   
    int i,m,w;
    if(n <= 1){
   
   
        return;
    }
    m = 2 * n - 1;    //数组共2n-1个元素
    HT = (HuffmanTree) malloc(sizeof(HTNode) * (m + 1));
    for(i = 1;i <= m;++i){
   
   
        //将所有元素的parent、lch、rch均设置为0
        HT[i].parent = 0;
        HT[i].lch = 0;
        HT[i].rch = 0;
    }
    for(i = 1;i <= n;++i){
   
   
        printf("请输入第%d个结点的权值:"\n,i);
        scanf("%d",&w);
        HT[i].weight = w;
    }

    //初始化完成，开始构造

    for(i = n + 1;i <= m;++i){
   
   
        //合并产生n-1个结点
        Select(HT,i - 1,&s1,&s2);

        //从森林中删除两棵左右子树
        HT[s1].parent = i;
        HT[s2].parent = i;
        //s1、s2分别作为i的左右孩子
        HT[i].lch = s1;
        HT[i].rch = s2;
        //i的权值为左右孩子权值之和
        HT[i].weight = HT[s1].weight + HT[s2].weight;
    }
}

void Select(HuffmanTree HT,int length,int* s1,int* s2){
   
   
    int i,j;
    *s1 = -1;
    for(i = 1; i < length; i++){
   
     //进行 n-1 次循环建立哈夫曼树  
        //s1表示森林中具有最小权值的树根结点的下标,s2为次最小的下标
        for(j = 0; j < length; j++){
   
     
            if (HT[j] != NULL && s1 == -1){
   
     
                *s1 = j;  
                continue;  
            }  
            if (HT[j] != NULL){
   
     
                *s2 = j;  
                break;  
            }  
        }  
}

算法有一定的难度，大家要根据前面的思路分析仔细体会，领悟到的话应该是比较简单的。

哈夫曼编码

在远程通讯中，我们往往需要将字符转换成由二进制表示的字符串，假设要传送的字符为：A B A C C D A。
若编码为：

A：00
B：01
C：10
D：11

则传送字符可以转换为：00 01 00 10 10 11 00。

这是一种定长的编码方式，该方式的缺点是耗费空间，每一种字符都需要定长的二进制表示，当字符很多的时候，空间的损耗无疑是巨大的。

我们可以考虑将传送信息中出现频率较高的字符采用尽可能短的编码，这样转换的二进制字符串便可能减少。

比如这样编码：

A：0
B：00
C：1
D：01

则传送字符可以转换为：0 00 0 10 10 11 00。

这是一种不定长的编码方式，可以发现，转换后的二进制字符串虽然减少了，但是出现了重码的情况。比如二进制字符串的前四位均为0，它可能会有以下几种解释：

AAAA
ABA
BB

这样会导致解码失败。

再次改良编码方式，即要设计长度不等的编码，但必须使任一字符的编码都不是另一个字符的编码的前缀，这种编码被称作前缀编码。

现在面临的问题是，什么样的前缀编码能使二进制字符串最短？
这样的编码就是哈夫曼编码。

统计字符集中每个字符在电文中出现的平均概率(概率越大，编码越短)
利用哈夫曼树的特点：权越大的叶子离根越近；将每个字符的概率值作为权值，构造哈夫曼树，则概率越大的结点，路径越短
在哈夫曼树的每个分支上标0或1(结点的左分支标0，右分支标1。把从根到每个叶子的路径上的标号连接起来，作为该叶子结点代表的字符的编码)

举个例子，比如要传输的字符集为D = {C,A,S,T,；}，字符出现频率w = {2,4,2,3,3}。

我们就要把字符出现的频率作为权值构造哈夫曼树，构造哈夫曼树已经难不倒大家了，直接贴出结果：
在这里插入图片描述
下面对哈夫曼树的分支进行标记，左分支标0，右分支标1：

这样就可以得出每个字符的编码了，即从根结点到目标结点所经过分支的编码。
则

T的编码为：00
；的编码为：01
A的编码为：10
C的编码为：110
S的编码为：111

因为哈夫曼树的特性，使得出现频率较高的字符处在了离根近的地方，这样也导致该字符的编码减短，这就是哈夫曼编码。

由此得出哈夫曼编码的两个性质：

性质一：哈夫曼编码是前缀码
性质二：哈夫曼编码是最优前缀码

哈夫曼编码算法实现

描述了哈夫曼编码的实现过程之后，最重要的还是算法实现，如何通过代码来实现这一算法过程呢？

//构造哈夫曼编码
void CreateHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n){
   
   
    char* cd;
    int i,start,c,f;
    //从叶子到根逆向求每个字符的哈夫曼编码，存储在编码表HC中
    HC = (char*) malloc(sizeof(n + 1));    //分配n个字符编码的头指针矢量
    cd = (char*) malloc(sizeof(n));        //分配临时存放哈夫曼编码的动态数组空间
    cd[n - 1] = '\0';                    //编码结束符
    for(i = 1;i <= n;++i){
   
                   //循环求解哈夫曼编码
        start = n - 1;                    
        c = i;
        f = HT[i].parent;
        while(f != 0){
   
                       //从叶子结点开始向上回溯，直至根结点
            --start;                    //回溯一次start--
            if(HT[f].lch == c){
   
               //结点c是f的左孩子
                cd[start] = '0';
            }else{
   
                           //结点c是f的右孩子
                cd[start] = '1';
            }        
            c = f;                        //继续回溯
            f = HT[f].parent;            
        }
        //为第i个字符串编码分配空间
        HC[i] = (char*) malloc(sizeof(n - start));
        //将求得的编码从临时空间cd复制到HC的当前行中
        strcpy(HC[i],&cd[start]);
    }
    //释放空间
    free(cd);
}

构建哈夫曼树的过程就不重复说了，之前已经深入分析过了。

哈夫曼树