赫夫曼树的特点

赫夫曼树的特点•1.权值越大的叶子离根越近，权值越小的叶结点越远离根结点。•2.具有n个叶子结点的赫夫曼树共有2n-1个节点。•3.赫夫曼树中没有度为1的结点。•严格的二叉树：没有度为1的结点的二叉树。三、哈夫曼树的构造算法•设置一个结构数组HuffmanTree保存哈夫曼树中各结点的信息，数组元素的结构形式如下：•typedefstruct{•unsingnedintweight;•unsingnedintparent,lchild,rchild;•}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树，0号单元不用•Typedefchar**HuffmanCode;//动态分配数组存储哈夫曼编码weightlchildrchildparent•其中，weight域保存结点的权值，lchild和rchild域分别保存该结点的左、右孩子结点在数组HuffmanTree中的序号，从而建立起结点之间的关系。为了判定一个结点是否已加入到要建立的哈夫曼树中，可通过parent域的值来确定。初始时parent的值为0，当结点加入到树中时，该结点parent的值为其双亲结点在数组HuffmanTree中的序号，就不会是0了。•构造哈夫曼树时，首先将由n个字符形成的n个叶结点存放到数组HuffmanTree的前n个分量中，然后根据前面介绍的哈夫曼方法的基本思想，不断将两个小子树合并为一个较大的子树，每次构成的新子树的根结点顺序放到HuffmanTree数组中的前n个分量的后面。•voidHaffmanTree(HuffmanTree&HT)•{/*哈夫曼树的构造算法*/•inti,j,s1,s2,m1,m2,n,m;•scanf(“%d”,&n);/*输入叶子结点个数*/•m=2*n-1;•HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode));•for(i=1;i=2*n-1;i++)/*数组初始化*/•{HT[i].weight=0;•HT[i].parent=0;•HT[i].lchild=0;•HT[i].rchild=0;•}•for(i=1;i=n;i++)scanf(“%d”,&HT[i].weight);/*输入n个叶子结点的权值*/•for(i=n+1;i=m;i++)/*构造哈夫曼树*/•{s1=s2=0;•m1=m2=10000;/*取最大权值为10000*/•for(j=1;j=i-1;j++)•{if(HT[j].weightm1&&HT[j].parent==0)•{m2=m1;s2=s1;•m1=HT[j].weight;s1=j;•}•elseif(HT[j].weightm2&&HT[j].parent==0)•{m2=HT[j].weight;•s2=j;•}•}/*查找权值最小且parent为0的两棵子树的序号s1s2*/••/*将找出的两棵子树合并为一棵子树*/HT[s1].parent=i;HT[s2].parent=i;•HT[i].lchild=s1;HT[i].rchild=s2;•HT[i].weight=HT[s1].weight+HT[s2].weigh;}•}四、哈夫曼树在编码问题中的应用•在数据通讯中，经常需要将传送的文字转换成由二进制字符0，1组成的二进制串，我们称之为编码。例如，假设要传送的电文为ABACCDA，电文中只含有A，B，C，D四种字符，•字符的四种不同的编码方案•字符编码字符编码字符编码字符编码•A000A00A0A01•B010B01B110B010•C100C10C10C001•D111D11D111D10总电文长度为21长度为14长度仅为13前缀编码:指的是，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的赫夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。如何设计一种编码，使得电文的总长度最短呢？具体做法如下：设需要编码的字符集合为{d1，d2，…，dn}，它们在电文中出现的次数或频率集合为{w1，w2，…，wn}，以d1，d2，…，dn作为叶结点，w1，w2，…，wn作为它们的权值，构造一棵哈夫曼树，规定哈夫曼树中的左分支代表0，右分支代表1，则从根结点到每个叶结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，我们称之为哈夫曼编码。在哈夫曼编码树中，树的带权路径长度的含义是各个字符的码长与其出现次数的乘积之和，也就是电文的代码总长，所以采用哈夫曼树构造的编码是一种能使电文代码总长最短的不等长编码。采用哈夫曼树进行编码，则不会产生二义性问题。因为，在哈夫曼树中，每个字符结点都是叶结点，它们不可能在根结点到其它字符结点的路径上，所以一个字符的哈夫曼编码不可能是另一个字符的哈夫曼编码的前缀，从而保证了译码的非二义性。实现哈夫曼编码的算法可分为两大部分：（1）构造哈夫曼树；（2）在哈夫曼树上求叶结点的编码。求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶结点开始，沿结点的双亲链域回退到根结点，每回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶结点所经过的路径上各分支所组成的0，1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求编码的高位码。//郝夫曼数和豪夫曼编码的存储表示typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanCode;Typedefchar**HuffmanCode;VoidHuffmanCoding((HuffmanTree&HT,HuffmanCode&HC,int*w,intn){//w存放n个字符的权值（均0)构造郝夫曼树HT，并求出n个字符的郝夫曼编码HC。If(n=1)return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//o号单元未用for(p=HT,i=1;i=n;++i,++p,++w)*p={*w,0,0,0};for(;i=m;++i,++p)*p={0,0,0,0};for(i=n+1;i=m;++i){//见郝夫曼树//在HT[0..i-1]选择parent为0且weight最小的两个结点，其序号分别为s1和s2。Select(HT,i-1,s1,s2);HT[s1].parent=i;HT[s2].parent=I;HT[i],lchild=s1;HT[i],lchild=s2;HT[i],weight=HT[s1],weight+HT[s2],weight;}//从叶子到根你想球每个字符的郝夫曼编码HC=(HuffmanCode)malloc((n+1)*sizeof(char*));cd=(char*)malloc(n*sizeof(char));cd[n-1]=“\0”;for(i=1;i=n;i++)/*求每个叶子结点的哈夫曼编码*/{start=n-1;c=i;p=HT[c].parent;while(p!=0)/*由叶结点向上直到树根*/{if(HT[p].lchild==c)cd.[--start]=“0”;elsecd.[--start]=“1”;c=p;p=HT[c].parent;}HC[i]=(char*)malloc((n-start)*sizeof(char));Strcopy(HC[i],&cd[start]);}Free(cd);}6．假设用于通信的电子由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10}（1）为这8个字母设计哈夫曼编码。（2）若用三位二进制数（0~7）对这个8个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几？它使电文总长平均压缩多少？例题HTweightparentlchildrchild170002190003200046000532000630007210008100009-00010-00011-00012-00013-00014-00015-000HTweightparentlchildrchild171100219130032900461000532140063900721130081011009510361011124911171218122814101113401527146015512151000131432211971062301000000111111fcdhaegba:1100b:00c:11110d:1110e:10f:11111g:01h:1101②哈夫曼编码码长：4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.1=2.71等长码长：3平均缩了(3-2.71)/3=10%a:1100b:00c:11110d:1110e:10f:11111g:01h:1101{0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10}{a,b,c,d,e,f,g,h}