《哈夫曼树构造》PPT课件.ppt
1/39,哈夫曼树构造及其编码,主讲人:程玉胜,数据结构精品资源共享课,2/39,内容提要,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,3/39,内容提要,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,4/39,二叉树、树、森林,N个结点的二叉树中结点空域的个数是【？】,证明的方法：从结点数和分支数两个角度来证明。,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,在一棵度为3的树中，其中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为 个,思考,树、森林到二叉树的相互转换,5/39,内容提要,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,6/39,内容提要,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,7/39,成绩判定问题 1,把下面成绩转换为5分制，计算不同的if语句比较的次数，假设100个学生。,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,第一种写法：if(cj6)cout“不及格”elseif(cj70)cout“及格”elseif(cj80)cout“中等”elseif(cj90)cout“良好”else cout“优秀”,8/39,成绩判定问题 2,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,对应的流程图：,(1)、计算2种方法在比较次数上的时间差异性：,1*5+2*15+3*40+4*30+4*10=315,3*5+3*15+2*40+2*30+2*20=220,(2)、哪个二叉树好？怎样保证比较次数最少呢？,最好的 最优二叉树,9/39,内容提要,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,10/39,内容提要,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,11/39,哈夫曼树的相关定义,树的带权路径长度定义为：树中所有叶子结点的带权路径长度之和 WPL(T)=wklk(对所有叶子结点),复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,最优二叉树（哈夫曼树）使 WPL最小的二叉树,WPL(T)=72+52+23+43+92=60,12/39,内容提要,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,13/39,内容提要,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,14/39,构造方法 1,假设给定n个权值的结点构造：,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,（1）：n个结点看成n颗树F（2）：在F中选取两个最小的结点，作为左 右子树，且根结点的权值等于左右子 树权值之和（3）：在F中删除这两颗树，并把刚得到的 二叉树加入F中（4）：重复（2）-（3），一棵树结束,15/39,构造方法 2,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,例,已知权值 W=5,6,2,9,7,9,5,6,2,7,5,2,7,6,9,7,6,7,13,9,16/39,构造方法 3,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,例,9,16,29,5个叶子结点，构造后有多少个结点？,17/39,构造算法 1,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,思考,有度为1的结点吗？，n个叶子结点构造的哈夫曼树有多少结点？,算法,数组 HT1m 存放结点 其中 m=2n-1 前n 个(1 n)为叶结点 最后一个为根结点数组 HC 1n 存放编码,18/39,构造算法 2,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,算法,void HuffmanCoding(HuffmanTree,例:设n=5,w=5,6,2,9,7，试设计 huffman(m=2*5-1=9),19/39,构造算法 2,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,5,2,7,6,9,7,6,7,13,9,20/39,构造算法 3,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,9,16,29,7 8 1 3,13 9 2 5,16 9 4 6,29 0 7 8,67687,21/39,构造算法 4,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,for(i=n+1;i=m;+i)/构造 Huffman树 Select(HT,i-1,s1,s2);/在HTk(1ki-1)中选择两个其双亲域为0,/且权值最小的结点,/并返回它们在HT中的序号s1和s2 HTs1.parent=i;HTs2.parent=i;/表示从F中删除s1,s2 HTi.lch=s1;HTi.rch=s2;/s1,s2分别作为i的左右孩子 HTi.weight=HTs1.weight+HTs2.weight;/i 的权值为左右孩子权值之和,22/39,内容提要,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,23/39,内容提要,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,24/39,HFM编码,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,9,16,29,0,0,0,0,1,1,1,1,00,01,11,100,101,25/39,HFM编码,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,/从叶子到根逆向求每个字符的哈夫曼编码HC=new CodeNoden+1;cd=new charn;cdn-1=0;/编码结束符for(i=1;i=n;+i)/依次求各叶子的编码 start=n-1;/编码起始位置 for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lch=c)cd-start=0;else cd-start=1;HCi.bits=new charn-start;/为第i个叶子分配空间 strcpy(HCi.bits,26/39,哈夫曼应用,复习 知识点引入 哈夫曼树相关定义 哈夫曼树构造 哈夫曼编码,已知某相同在通信联络中只可能出现8种可能字符，其概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11.假设待发报文长度为100个字符，请选择最短报文，并计算发送报文的长度。,例,27/39,谢谢!,欢迎通过数据结构精品课程网站http:/210.45.168.34:8080/08/sjjg/Learning/SelfLearningDS/index.asp,Thanks for Your Attention,
