数据结构（双语）18-哈夫曼树的构建及应用-编码译码

DataStructure

数据结构计算机与信息技术系袁莹QQ:10232828Addr:综合楼401

2016年05月04日*Huffmantree一、哈夫曼树的定义及建立

结点的路径长度（lengthofpath）就是从根结点到每个结点的路径长度，其值为路经上的边数。赋予了权值的结点的路径长度与该结点权值的乘积即为结点的带权路径长度（WeightedPathLengthofNode）。树的带权路径长度（WeightedPathLengthofTree，缩写为WPL）定义为：树中所有叶子结点的带权路径长度之和，记为：其中n表示叶子结点数，wi表示第i个叶子结点的权值，li代表第i个叶子结点的路径长度。WPLa=2×2+3×2+6×2+8×2=38WPLb=8×1+6×2+2×3+3×3=35WPLc=2×1+6×3+8×3+3×2=50WPLd=8×1+2×3+3×3+6×2=35哈夫曼树（HuffmanTree）又称最优二叉树，是在含有n个叶子结点，权值分别为w1，w2，……，wn的所有二叉树中，带权路径长度WPL最小的二叉树。哈夫曼（D.A.Huffman）在上世纪五十年代初便提出了一个非常简单的算法来建立哈夫曼树，其算法描述如下：（1）将给定的n个权值{w1，w2，...，wn}作为n个根结点的权值，构造一个具有n棵二叉树的森林{T1，T2，...，Tn}，其中每棵二叉树只有一个根结点；（2）在森林中选取两棵根点权值最小的二叉树分别作为左、右子树，增加一个新结点作为根，从而将两棵树合并成一棵树，新根结点的权值为左右子树根结点权值之和。森林中因此也减少了一棵树；（3）重复上面步骤（2）的处理过程，直到森林中只有一棵二叉树为止，这棵二叉树就是哈夫曼树。Huffmantree从哈夫曼树构造过程和生成结果可知，哈夫曼树具有以下特点：（1）哈夫曼树不唯一。（2）哈夫曼树中只包含度为0和度为2的结点。（3）树中权值越大的叶子结点离根结点越近。例

假设树中叶子结点的权值为{5,29,7,8,14,23,3,11}，构造一棵哈夫曼树。（1）将给定的8个权值作为根结点，构造具有8棵树的森林（2）从森林中选取根点权值最小的两棵二叉树3、5，分别作为左右子树，构造一棵新的二叉树，新树根点权值为8，森林中减少一棵树。（3）重复步骤（2），直到森林中只剩一棵二叉树为止。Huffmantree方便查找双亲，将哈夫曼树的存储结构设计为三叉链表。每个结点包含四个域：weight为结点的权值，lchild、rchild、parent分别为左、右孩子和双亲结点的指针。含有N个叶子结点的哈夫曼树共有2N-1个结点，由此可定义一个长度为2N-1的数组tree来存储哈夫曼树，下标从1开始，0代表指针空（NULL）。weightparentlchildrchildtypedefstruct /*哈夫曼树结点的存储结构*/{ floatweight; /*结点的权值*/ intparent; /*双亲在数组中的下标*/ intlchild,rchild;/*左右孩子在数组中的下标*/}HufmTree;HufmTreetree[2N];在上述存储结构上实现哈夫曼算法的过程如下：（1）将哈夫曼树数组tree中的2N-1个结点初始化：即将各结点的权值、双亲、左孩子、右孩子均置为0。（2）读入N个叶子结点的权值，分别存入数组tree[i]（1≤i≤N）的权值域中，构造包含N棵树的初始森林，森林中的每棵树只有一个根结点。（3）循环N-1次，对森林中的树进行N-1次合并，产生N-1个新结点，依次放入数组tree[i]中（N+1≤i≤2N-1）。每次合并的步骤是：1）在当前森林的所有结点tree[j]（1≤j≤i-1）中，选取具有最小权值和次小权值的两个根结点（parent域为0的结点），分别用p1和p2记住这两个根结点在数组tree中的下标。2）将根为tree[p1]和tree[p2]的两棵树合并，使其成为新结点tree[i]的左、右孩子，得到一棵以新结点tree[i]为根的二叉树即将tree[i].weight赋值为tree[p1].weight和tree[p2].weight之和tree[i]的左指针赋值为p1；tree[i]的右指针赋值为p2；同时将tree[p1]和tree[p2]的双亲域均赋值为i，使其指向新结点tree[i]即它们在当前森林中已不再是根结点。

二、哈夫曼编码及译码在进行文字传输时，数据通信的发送方需要将原文中的每一个文字转换成对应的二进制0、1序列（编码）进行发送，接收方接收到二进制的0、1串后再还原成原文（译码）。其编码和译码的过程如下所示：原文

电文（二进制的0、1序列）

原文常用的编码方式有两种：等长编码和不等长编码。等长编码：ASCⅡ码，其特点是每个字符的编码长度相同。编码简单且具有唯一性，当字符集中的字符在电文中出现的频度相等时，它是最优的编码。不等长编码：字符的编码长度不等，因此称这种编码方式为不等长编码。为了使译码唯一，则要求字符集中任一字符的编码都不是其他字符编码的前面一部分，这种编码叫做前缀（编）码。二、哈夫曼编码及译码利用二叉树来对叶子结点进行编码，所得的编码一定为前缀码。若要使报文总长最短，则利用哈夫曼树对叶子结点进行编码一定是最优的编码。哈夫曼编码的实现方法如下：（1）利用字符集中每个字符的使用频度作为权值构造一个哈夫曼树；（2）从根结点开始，与左孩子的连线标上0，与右孩子的连线标上1；（3）由根到某叶子结点的路经上的0、1序列组成该叶子结点的编码。例

假设有一个字符集包含8个字符：{a,b,c,d,e,f,g,h}，每个字符的使用频度（权值）分别为{5,29,7,8,14,23,3,11}，为每个字符设计哈夫曼编码。字符编码a0001b10c1110d1111e110f01g0000h001哈夫曼编码的实现算法首先根据字符的权值构建哈夫曼树，然后从每个叶子结点开始不断的向上搜索双亲结点，直到根点为止，得出字符的哈夫曼编码。编码的存储结构及实现算法的C函数描述如下：typedefstruct /*哈夫曼编码的存储结构*/{ charbits[N]; /*保存编码的数组*/intstart; /*编码的有效起始位置*/charch; /*字符*/}CodeType;CodeTypecode[N+1];/*字符编码数组*/

huffmanCode(HufmTreetree[],CodeTypecode[]) /*利用哈夫曼树求字符的哈夫曼编码*/{inti,c,p;for(i=1;i<=N;i++)/*N次循环，分别得到N个字符的编码*/{ code[i].start=N;c=i;p=tree[i].parent; /*获取字符的双亲*/while(p!=0) /*一直往上层查找，直到根结束*/{code[i].start—;if(tree[p].lchild==c)code[i].bits[code[i].start]='0';elsecode[i].bits[code[i].start]='1';c=p;p=tree[p].parent;}}}哈夫曼译码的实现算法与编码过程相反，译码过程是从哈夫曼树的根结点出发，逐个读入电文中的二进制码，若读入0，则走向左孩子，否则走向右孩子，一旦达到叶结点，便译出相应的字符。然后，重新从根结点出发继续译码，直到二进制电文结束。decode(HufmTreetree[],CodeTypecode[]) { /*已知哈夫曼树和哈夫曼编码，对输入的01码进行译码*/inti=m,b; /*i=m表示从根点出发进行译码*/intendflag=-1; /*标识是否结束*/intyiflag; /*标识是否刚好译出一个字符*/scanf("%d",&b); /*获取输入的第一个01码*/while(b!=endflag) /*依次输出译出的字符，直到遇到结束符为止*/{ yiflag=0;if(b==0) i=tree[i].lchild; /*读入0往左走*/else i=tree[i].rchild; /*读入1往右走*/if(tree[i].lchild==0) /*走到叶子结点，译出字符*/{printf("%c",code[i].ch);i=m; /*重新从根点出发，准备译下一个字符*/yiflag=1;}scanf("%d",&b);}if(yiflag!=1)printf(“\nERROR\n”); /*输入错误*/}if(a<60)b=“bad”;elseif(a<70)b=“pass”; elseif(a<80)b=“general”; elseif(a<90)b=“good”; elseb=“excellent”;哈夫曼树的应用

——百分制转换成五级分制的程序可用判定树来表示假设分布规律如下：假定以5,15,40,30,10为权构造一棵有5个叶子节点的哈夫曼树分数0-5960-6970-7980-8990-100比例数0.050.150.400.300.10五级分制