《哈夫曼树构造》PPT课件

《《哈夫曼树构造》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1/39哈夫曼树构造及其编码主讲人:程玉胜2013.11.29《数据结构》精品资源共享课2/39内容提要复习知识点引入哈夫曼树相关定义哈夫曼树构造哈夫曼编码复习知识点引入哈夫曼树相关定义哈夫曼树构造哈夫曼编码3/39内容提要复习知识点引入哈夫曼树相关定义哈夫曼树构造哈夫曼编码复习知识点引入哈夫曼树相关定义哈夫曼树构造哈夫曼编码4/39二叉树、树、森林N个结点的二叉树中结点空域的个数是【？】证明的方法：从结点数和分支数两个角度来证明。复习知识点引入哈夫曼树相关定义哈夫曼树构造哈夫曼编码在一棵度为3的树中，其中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数

2、为2个，则度为0的结点数为个思考树、森林到二叉树的相互转换5/39内容提要复习知识点引入哈夫曼树相关定义哈夫曼树构造哈夫曼编码复习知识点引入哈夫曼树相关定义哈夫曼树构造哈夫曼编码6/39内容提要复习知识点引入哈夫曼树相关定义哈夫曼树构造哈夫曼编码复习知识点引入哈夫曼树相关定义哈夫曼树构造哈夫曼编码7/39成绩判定问题1把下面成绩转换为5分制，计算不同的if语句比较的次数，假设100个学生。复习知识点引入哈夫曼树相关定义哈夫曼树构造哈夫曼编码60分以下60-6970-7980-8990分以上5%15%40%30%10%第一种写法：if(cj<6)cout<<“不及格

3、”elseif(cj<70)cout<<“及格”elseif(cj<80)cout<<“中等”elseif(cj<90)cout<<“良好”elsecout<<“优秀”8/39成绩判定问题2复习知识点引入哈夫曼树相关定义哈夫曼树构造哈夫曼编码60分以下60-6970-7980-8990分以上5%15%40%30%10%对应的流程图：(1)、计算2种方法在比较次数上的时间差异性：1*5+2*15+3*40+4*30+4*10=3153*5+3*15+2*40+2*30+2*20=220(2)、哪个二叉树好？怎样保证比较次数最少呢？最好的最优二叉树9/39内容提要

4、复习知识点引入哈夫曼树相关定义哈夫曼树构造哈夫曼编码复习知识点引入哈夫曼树相关定义哈夫曼树构造哈夫曼编码10/39内容提要复习知识点引入哈夫曼树相关定义哈夫曼树构造哈夫曼编码复习知识点引入哈夫曼树相关定义哈夫曼树构造哈夫曼编码11/39哈夫曼树的相关定义树的带权路径长度定义为：树中所有叶子结点的带权路径长度之和WPL(T)=wklk(对所有叶子结点)复习知识点引入哈夫曼树相关定义哈夫曼树构造哈夫曼编码最优二叉树（哈夫曼树）使WPL最小的二叉树WPL(T)=72+52+23+43+92=6012/39内容提要复习知识点引入哈夫曼树相关定义哈夫曼树构造哈夫

5、曼编码复习知识点引入哈夫曼树相关定义哈夫曼树构造哈夫曼编码13/39内容提要复习知识点引入哈夫曼树相关定义哈夫曼树构造哈夫曼编码复习知识点引入哈夫曼树相关定义哈夫曼树构造哈夫曼编码14/39构造方法1假设给定n个权值的结点构造：复习知识点引入哈夫曼树相关定义哈夫曼树构造哈夫曼编码（1）：n个结点看成n颗树F（2）：在F中选取两个最小的结点，作为左右子树，且根结点的权值等于左右子树权值之和（3）：在F中删除这两颗树，并把刚得到的二叉树加入F中（4）：重复（2）-（3），一棵树结束15/39构造方法2复习知识点引入哈夫曼树相关定义哈夫曼树构造哈夫曼编码例已知权值W={

6、5,6,2,9,7}956275276976713952716/39构造方法3复习知识点引入哈夫曼树相关定义哈夫曼树构造哈夫曼编码例9527166713295个叶子结点，构造后有多少个结点？17/39构造算法1复习知识点引入哈夫曼树相关定义哈夫曼树构造哈夫曼编码思考有度为1的结点吗？，n个叶子结点构造的哈夫曼树有多少结点？算法rchlchparentweight结点结构：数组HT[1．．m]存放结点其中m=2n-1前n个(1~n)为叶结点最后一个为根结点数组HC[1．．n]存放编码18/39构造算法2复习知识点引入哈夫曼树相关定义哈夫曼树构造哈夫曼编码算法void

7、HuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,intn){if(n<=1)return;m=2*n-1;HT=newHTNode[m+1];//0号单元未用，HT[m]表示根结点for(i=1;i<=n;++i)cin>>HT[i].weight;for(i=1;i<=m;++i){HT[i].lch=0;HT[i].rch=0;HT[i].parent=0;}例:设n=5,w={5,6,2,9,7}，试设计huffman(m=2*5-1=9)WeightParentLchildRchild1500026000320004

8、90005