方案一：二叉树的建立和遍历具体内容：先生成一棵二叉树,ppt课件

1,方案一：二叉树的建立和遍历具体内容：先生成一棵二叉树，再用中序遍历方式打印每个结点值，并统计其叶子结点的个数。方案二：哈夫曼树的建立和编码器的实现具体内容：先生成一棵哈夫曼树，再打印各字符对应的哈夫曼编码。方案三：哈夫曼编/译码器的设计与实现具体内容：参见严题集P149实习5.2要求，或参见自测卷,第二次上机内容预告：（三个方案由易到难，可自选，参见自测题集实验二资料）,2,第6章树和二叉树作业（共11题）76.256.266.296.426.436.476.496.65,喻信课堂网址：8:8000/海豚之家网址：,3,第6章树和二叉树（Treei=10,a=110,n=111，则：,明确：要实现Huffman编码，就要先构造Huffman树,讨论：Huffman树有什么用？,权值大的结点用短路径，权值小的结点用长路径。,WPL最小的树,频度高的信息用短码，反之用长码，传输效率肯定高！,WPL2=1bit72bit5+3bit(2+4)=35,最小冗余编码、信息高效传输,14,2.构造Huffman树的步骤（即Huffman算法）：,(1)由给定的n个权值w1,w2,wn构成n棵二叉树的集合F=T1,T2,Tn（即森林），其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均空。(2)在F中选取两棵根结点权值最小的树做为左右子树构造一棵新的二叉树，且让新二叉树根结点的权值等于其左右子树的根结点权值之和。(3)在F中删去这两棵树，同时将新得到的二叉树加入F中。(4)重复(2)和(3),直到F只含一棵树为止。这棵树便是Huffman树。,怎样证明它就是WPL最小的最优二叉树？参考信源编码,Huffman树的特点：没有度为1的结点。,15,step1：对权值进行合并、删除与替换在权值集合7,5,2,4中，总是合并当前值最小的两个权,具体操作步骤：,a.初始,方框表示外结点（叶子，字符）,圆框表示内结点（合并后的权值）,b.合并24,c.合并56,d.合并711,16,step2：按左“0”右“1”对Huffman树的所有分支编号,Huffman编码结果：d=0,i=10,a=110,n=111WPL=1bit72bit5+3bit(2+4)=35（小于等长码的WPL=36）,特征：每一码不会是另一码的前缀，译码时可惟一复原,Huffman编码也称为前缀码,将Huffman树与Huffman编码挂钩,17,二、Huffman编码,（1）由于Huffman树的WPL最小，说明编码所需要的比特数最少。,（4）Huffman编码时是从叶子走到根；而译码时又要从根走到叶子，因此每个结点需要增开双亲指针分量（连同结点权值共要开5个分量）（5）用计算机实现时，顺序和链式两种存储结构都要用到。,分析Huffman树和编码的特点：,霍夫曼编码的基本思想是出现概率大的信息用短码，概率小的用长码,最小冗余,这种编码已广泛应用于网络通信中。,（2）Huffman树肯定没有度为1的结点；（3）一棵有n0个叶子结点的Huffman树，共有2n0-1个结点；（因为n=n0+n1+n2=2n0-1),18,如何编程实现Huffman编码？,建议1：Huffman树中结点的结构可设计成5分量形式：,将整个Huffman树的结点存储在一个数组HT1.n.m中;各叶子结点的编码存储在另一“复合”数组HC1.n中。请参见教材P149图6.27的（a)和（c),建议2：Huffman树的存储结构可采用顺序存储结构：,(1)教材P147149内容；(2)严蔚敏“数据结构”演示程序；(3)习题集P149实习5.2要求；(4)自测卷第6章上机方案二的源程序。,可参考：,19,typedefstructunsignedintweight；/权值分量（可放大取整）unsignedintparent，lchild，rchild；/双亲和孩子分量HTNode，*HuffmanTree；/用动态数组存储Huffman树typedefchar*HuffmanCode；/动态数组存储Huffman编码表,Huffman树和Huffman树编码的存储表示：,双亲,*HuffmanTree或HT向量,HT3.parent=9,指针型指针,20,如何编程实现Huffman编码？,参见教材P147,先构造Huffman树HT，再求出N个字符的Huffman编码HC。,VoidHuffmanCoding(HuffmanTreem=2*n-1;/n0个叶子的HuffmanTree共有2n0-1个结点；HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);/0单元未用,*w存放n个字符的权值,for(p=HT,i=1;i=n;+i,+p,+w)*p=*w,0,0,0;/给前n0个单元初始化for(；i=m;+i,+p)*p=0,0,0,0;/对叶子之后的存储单元清零for(i=n+1;i=m;+i)/建Huffman树(从叶子后开始存内结点)Select(HT,i-1,s1,s2);/在HT1i-1选择parent为0且weight最小的两个结点，其序号分别为S1和s2（教材未给出此函数源码）HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;,21,(续前)再求出n个字符的Huffman编码HC,HC=(HuffmanCode)malloc(n+1)*sizeof(char*);/分配n个字符编码的头指针向量（一维数组）cd=(char*)malloc(n*sizeof(char);/分配求编码的工作空间(n)cdn-1=“0”;/编码结束符（从cd0cdn-1为合法空间）for(i=1;i=n;+i)/逐个字符求Huffman编码start=n-1;/编码结束符位置for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)/从叶子到根逆向求编码if(HTf.lchild=c)cd-start=“0”;elsecd-start=“1”;HCi=(char*)malloc(n-start)*sizeof(char);/为第i个字符编码分配空间strcpy(HCi,/释放工作空间/HuffmanCoding,22,Huffman编码举例,解：先将概率放大100倍，以方便构造哈夫曼树。放大后的权值集合w=7,19,2,6,32,3,21,10，按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树。,例1【严题集6.26】：假设用于通信的电文仅由8个字母a,b,c,d,e,f,g,h构成，它们在电文中出现的概率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10，试为这8个字母设计哈夫曼编码。如果用07的二进制编码方案又如何？【类同P148例2】,23,w=7,19,2,6,32,3,21,10在机内存储形式为:,b,c,a,d,e,g,f,h,请注意：哈夫曼树样式不惟一！,5,11,17,28,40,60,100,双亲,左右孩子,24,对应的哈夫曼编码：,Huffman码的WPL2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61,3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3,二进制等长码的WPL,按左0右1标注,25,另一种表示：,26,小结：哈夫曼树及其应用,1.Huffman算法的思路：权值大的结点用短路径，权值小的结点用长路径。,2.构造Huffman树的步骤：对权值的合并、删除与替换,3.Huffman编码规则：左“0”右“1”又称为前缀码、最小冗余编码、紧致码等等，它是数据压缩学的基础。