第6章 树和二叉树3

16.8哈夫曼树与哈夫曼编码最优树的定义如何构造最优树前缀编码2有关术语•路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。•路径长度：路径上的分支数•树的路径长度：从树根到每一个结点的路径长度之和•树的带权路径长度：树中所有带权结点的路径（WeightedPathLength）长度之和。rdcab2475例如：第k个叶子结点到根的路径长度—个叶子结点的权值第—叶子结点的个数其中：记作：kWPL1kknklwnlkwk-==3例有4个结点a,b,c,d，其权值分别为7，5，2，4，构造有4个叶子结点的二叉树abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35==nkKKLWWPL1VS4哈夫曼树（Huffman树）——又称最优二叉树，它是n个带权叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉树。教材定义：设有n个权值{w1,w2,……wn}，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi,则WPL最小的二叉树叫哈夫曼树或最优二叉树。5构造哈夫曼树Huffman给出构造最优二叉树的算法，具体构造哈夫曼算法的步骤如下：⑴根据给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树Ti(1≤i≤n)中只有一个带权为wi的根结点，其左右子树均空；⑵在F中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。⑶在F中删除这两棵树，同时将新得到的二叉树加入F中。重复(2)和(3)，直到F只含一棵树为止。这棵树便是所求的赫夫曼树。6例如，对5个权值{5,6,2,9,7}构造最优二叉树的过程如动画所示79例如:已知权值W={5,6,2,9,7}562752769767139527867139527952716671329000011110001101101119例：编制一个将百分制转换成五级分制的程序0～59————————————————————bad60～69————————————————————pass70～79————————————————————general80～89————————————————————good90～100————————————————————excellentHuffman树的应用：寻求最佳判断过程if(a60)b=“bad”;elseif(a70)b=“pass”;elseif(a80)b＝“general”;elseif(a90)b=“good”;elseb=“excellent”;………………………5%………………………15%………………………40%………………………30%………………………10%a60不及格YNa70及格YNa80中等YNa90良好YN优秀根据出现的频率决定比较的次数判定树10出现的频率：10153040515510153030604010070～7980～890～5960～6990～10070≤a80YN中等80≤a90YN良好60≤a70NY及格a60YN优秀不及格11改造成每个判定框只有一次比较的判定树：a80YNa90YN良好Y及格a60YN优秀不及格a70N中等实践证明：按照此棵判定树，输入10000个输入数据，原判定树需进行31500次比较，此判定树需进行22000次比较126.6.2赫夫曼编码在电报通讯中，电文是以二进制的0，1序列传送的。编码：在发送端，发送的电文二进制序列译码：在接收端，接到的二进制序列电文13赫夫曼编码提出的背景：（1）如何使电报编码变短，非前缀编码会出现二义性；（2）用二叉树可以构造前缀编码；（3）由哈夫曼树得到最优编码赫夫曼(Huffman)编码是一种常用的压缩编码方法，是Huffman于1952年为压缩文本文件建立的。它的基本原理是频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代替，每个数据的代码各不相同。这些代码都是二进制码，且码的长度是可变的。14编码方式：1）等长编码例：假设传送的电文为英文序列‘ABACCDA’ABCD00011011则电文编码为“00010010101100”，总长14，译码时：两位一分152）不等长编码一般，在英文字母a—z中，e的使用频率比q,z要大得多使用频率高的用短码使用频率低的用长码使用频率：3121ABCD000110电文编码“000011010”，总长9译码：AAAA或BB或ABA原因：A(0)为B(00)的前缀编码不等长，但大部分情况下电文长度会减少16如何得到使电文长度最短的二进制前缀编码？假设电文中每种字符出现的次数为Wi,其编码长度为li,电文中有n种字符，则电文总长为：iniilw=1设计不等长编码时，任一字符的编码不是另一字符编码的前缀，这种编码称为前缀编码。使它最小，对应到二叉树上，置Wi为叶子的权li为根到叶子的路径长度则设计电文总长最短的问题变成设计赫夫曼树的问题3）前缀编码17010101哈夫曼编码：约定:树中的左分支表示字符‘0’树中的右分支表示字符‘1’编码：从根到叶子的路径上分支字符组成的字符串作为该叶子结点字符的编码。例：A:3B:1C:2D:1则：A：0C：10B：110D：111由此可见该编码是前缀编码待传电文ABACCDA的编码：‘0110010101110’，总长13ACBD18思想：根据字符出现频率编码，使电文总长最短编码：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列例要传输的字符集D={C,A,S,T,;}字符出现频率w={2,4,2,3,3}CS3364224814T;A00110110T:00;:01A:10C:110S:111Huffman编码：数据通信用的二进制编码19译码：从Huffman树根开始，从待译码电文中逐位取码。若编码是“0”，则向左走；若编码是“1”，则向右走；一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束例电文编码：‘0110010101110’ACBD011100译文只能是“ABACCDA”注意：编码方和译码方的哈夫曼树必须一致，否则不能正确译码20哈夫曼编码算法的实现首先要清楚2个问题：•由n个叶子结点构成的哈夫曼树共有多少个结点？有多少度为2的结点？•n个结点经过n-1次合并，得到一棵哈夫曼树，每次和并得到一个新结点。共计:n+n-1=2n-1•度为2的结点个数：n-1•哈夫曼树有没有度为1的结点？•没有，仅有度为2的结点和叶子结点21哈夫曼编码算法的实现一棵有n个叶子的哈夫曼树共有2n-1个结点，可以用一个大小为2n-1的一维数组存放哈夫曼树的各个结点。由于每个结点同时还包含其双亲信息和孩子结点的信息，所以构成一个静态三叉链表。静态三叉链表描述如下：typedefstruct{intweight;/*用来存放各个结点的权值*/intparent,LChild,RChild;/*指向双亲、孩子结点的指针*/}HTNode,*HuffmanTree;typedefchar**HuffmanCode;/*动态分配数组存储哈夫曼编码*/22对Huffman编码器程序的解释：一、构造Huffman树二、输出Huffman编码注1：算法开始时，把每个子树的双亲设为空。注2：各个子树权值序列并没有重新排序，而是顺序存放。挑选两个最小权值是用逐次比较法，用s1和s2记录对应位置；注3：合并后生成的新树依次顺序存放，它的两个子树并不删除，而是修改这两个子树的双亲指针（i）；下一轮找最小权值时，凡是双亲指针不空的就跳过去（不再考虑）。注：从叶子开始按“左0右1”将每个叶子的哈夫曼码存入对应数组（为每个叶子设立一个向量，从“个位”开始存放）。HT[s1].parent=?23例6-2八种字符,其频率分别为:0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11500029000700080001400023000300011000000000000000000000000HT.weightparentlchildrchild1234567891011121314155900291400710008100014120023130039001111008111715123419138929145104215611581521210001314HT.weightparentlchildrchild12345678910111213141524创建哈夫曼树并求哈夫曼编码的算法如下：HuffmanTreeCrtHuffmanTree(HuffmanTree*ht,HuffmanCode*hcode,int*w,intn){/*w存放n个权值,构造哈夫曼树ht,并求出哈夫曼编码hc*/HuffmanTreeht;m=2*n-1;ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode));/*0号单元未使用*/for(i=1;i=n;i++)ht[i]={w[i],0,0,0};/*叶子结点初始化，数组前n个*/for(i=n+1;i=m;i++)ht[i]={0,0,0,0};/*非叶子结点初始化，数组后n-1个*/25for(i=n+1;i=m;i++)/*创建非叶子结点,建哈夫曼树*/{/*在ht［1］~ht［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］.RChild=s2;ht［i］.weight=ht［s1］.weight+ht［s2］.weight;}/*哈夫曼树建立完毕*//*从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码*/hcode=(HuffmanCode)malloc((n+1)*sizeof(char*));/*分配n个编码的头指针*/cd=(char*)malloc(n*sizeof(char));/*分配求当前编码的工作空间*/cd［n-1］＝′\0′；/*从右向左逐位存放编码，首先存放编码结束符*/26for(i=1;i=n;i++)/*求n个叶子结点对应的哈夫曼编码*/{start=n-1;/*初始化编码起始指针*/for(c=i,p=ht［i］.parent;p!=0;c=p,p=ht［p］.parent)/*从叶子到根结点求编码*/if(ht［p］.LChild==c)cd［--start］=′0′;/*左分支标0*/elsecd［--start］=′1′;/*右分支标1*/hcode［i］=(char*)malloc((n-start)*sizeof(char));/*为第i个编码分配空间*/strcpy(hcode［i］,&cd［start］);}free(cd);}27数据结构课程的内容28本章小结1、定义和性质2、存储结构3、遍历4、线索化：线索树顺序结构链式结构二叉链表线索链表先序线索树中序线索树后序线索树树二叉树森林先序遍历后序遍历遍历存储结构遍历双亲表示孩子表示孩子兄弟先序遍历后序遍历中序遍历后序遍历先序遍历哈夫曼树哈夫曼编码29复习：课堂练习1、简述线性结构与非线性结构的不同点。2、给定二叉树的两种遍历序列，前序遍历序列：D，A，C，E，B，H，F，G，I；中序遍历序列：D，C，B，E，H，A，G，I，F；试画出二叉树。该二叉树是不是唯一的？若给定先序遍历序列和后序遍历序列，能不能唯一确定一棵二叉树呢？3、假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分