数据结构课件哈夫曼树

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

1、算法与数据结构6.树与二叉树-----6.6哈夫曼树1．路径和路径长度在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。6.6哈夫曼树一、基本术语ABCDEFG2．结点的权及带权路径长度给树的结点附加的这个有着某种意义的实数，称为该结点的权（weight）。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。ABCDEFG4125373．树的带权路径长度树的带权路径长度规定

2、为所有叶子结点的带权路径长度之和，记为wpl=其中n为叶子结点数目，wi为第i个叶子结点的权值，li为第i个叶子结点的路径长度。二、构造哈夫曼树1．哈夫曼树的定义在一棵二叉树中，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffmantree)。例有4个结点，权值分别为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=

3、35要使二叉树WPL小,就须在构造树时,将权值大的结点靠近根.2应用举例在求得某些判定问题时，利用哈夫曼树获得最佳判定算法。例编制一个将百分制转换成五分制的程序。最直观的方法是利用if语句来的实现。if(x<60)score=’不及格’;elseif(x<70)score=’及格’;elseif(x<80)score=’中’;elseif(x<90)score=’良’;elsescore=’优’;a80a90不及格良好中等及格a60a70优秀判定树按图的判定过程:转换一个分数所需的比较次数=从根到对应

4、结点的路径长度转换10000个分数所需的总比较次数=10000(0.051+0.152+0.43+0.34+0.14）二叉树的带权路径长度优秀a80a90不及格良好中等及格a60a70分数0-5960-6970-7980-8990-100比例数0.050.150.400.300.10设有10000个百分制分数要转换，设学生成绩在5个等级以上的分布如下：构造以分数的分布比例为权值的哈夫曼树3．哈夫曼树的构造假设有n个权值，则构造出的哈夫曼树有n个叶子结点。n个权值分别设为w1,w2,…,wn

5、,则哈夫曼树的构造规则为：(1)将w1,w2,…,wn看成是有n棵树的森林(每棵树仅有一个结点)；(2)在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；(3)从森林中删除选取的两棵树，并将新树加入森林；(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为我们所求得的哈夫曼树。构造哈夫曼树的模拟演示下面给出哈夫曼树的构造过程，假设给定的叶子结点的权分别为1,5,7,3，则构造哈夫曼树过程如图所示。n个权值构造哈夫曼树需n-1次合并，每

6、次合并，森林中的树数目减1，最后森林中只剩下一棵树，即为我们求得的哈夫曼树。n个权值构造哈夫曼树需?次合并例：W（权）={2,4,2,3,3}，叶子结点个数m=5试设计Huffman树。哈夫曼树的算法模拟演示3、哈夫曼树构造程序一棵有n个叶子结点的Huffman树有2n-1个结点顺序存储结构—一维结构数组存储结点信息，结点类型定义为：typedefstruct{intweight;intparent,lchild,rchild;}JD;#defineMAX100voidhuffman(intn,intw[],

7、JDt[]){inti,j,k,x1,x2,m1,m2;for(i=1;i<(2*n);i++){t[i].parent=t[i].lchild=t[i].rchild=-1;if(i<=n)t[i].weight=w[i];elset[i].weight=0;}for(i=1;i

8、=j;}elseif((t[j].weight