数据结构哈夫曼树学习教案.pptx
会计学1数据结构数据结构(sh j ji u)哈夫曼树哈夫曼树第一页，共21页。1 1路径和路径长度路径和路径长度在在一一棵棵树树中中，从从一一个个结结点点往往下下可可以以达达到到的的孩孩子子或或子子孙孙(z(z sn)sn)结结点点之之间间的的通通路路，称称为为路路径径。通通路路中中分分支支的的数数目目称称为为路路径长度。径长度。若若规规定定根根结结点点的的层层数数为为1 1，则则从从根根结结点点到到第第L L层层结结点点的的路路径径长度为长度为L-1L-1。6.6 6.6 哈夫曼树哈夫曼树一、基本一、基本(jbn)术语术语ABCDEFG第1页/共21页第二页，共21页。2 2 2 2结点的权及带权路径结点的权及带权路径结点的权及带权路径结点的权及带权路径(ljng)(ljng)(ljng)(ljng)长度长度长度长度n n给树的结点附加的给树的结点附加的这个有着某种意义这个有着某种意义的实数，称为该结的实数，称为该结点的权（点的权（weight）。）。n n结点的带权路径长结点的带权路径长度度(chngd)为：从为：从根结点到该结点之根结点到该结点之间的路径长度间的路径长度(chngd)与该结点与该结点的权的乘积。的权的乘积。ABCDEFG412537第2页/共21页第三页，共21页。3树的带权路径长度树的带权路径长度树树的的带带权权路路径径长长度度规规定定为为所所有有(suyu)叶叶子子结结点点的的带权路径长度之和，记为带权路径长度之和，记为wpl=其其中中n 为为叶叶子子结结点点数数目目，wi为为第第i 个个叶叶子子结结点点的的权权值，值，li 为第为第i 个叶子结点的路径长度。个叶子结点的路径长度。二、构造二、构造(guzo)哈夫曼树哈夫曼树1哈夫曼树的定义哈夫曼树的定义在在一一棵棵二二叉叉树树中中，若若带带权权路路径径(ljng)长长度度达达到到最最小小，称称这这样样的二叉树为最优二叉树，也称为哈夫曼树的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。第3页/共21页第四页，共21页。例例 有有4个结点个结点(ji din)，权值分别为，权值分别为7，5，2，4，构造有，构造有4个叶子结点个叶子结点(ji din)的二叉树的二叉树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要使二叉树要使二叉树WPL小小,就须在构造就须在构造树时树时,将权值大的将权值大的结点结点(ji din)靠近根靠近根.第4页/共21页第五页，共21页。2 2 应用举例应用举例在求得某些判定问题时，利用在求得某些判定问题时，利用(lyng)(lyng)哈夫曼树获得最佳判哈夫曼树获得最佳判定算法。定算法。例例 编制一个将百分制转换成五分制的程序。编制一个将百分制转换成五分制的程序。最直观的方法是利用最直观的方法是利用(lyng)if(lyng)if语句来的实现。语句来的实现。if(x60)score=不及格不及格(j g);else if(x70)score=及格及格(j g);else if(x80)score=中中;else if(x90)score=良良;else score=优优;a a 80 80a a 90 90不及格不及格良好良好中等中等及格及格a a 60 60a a 70 70优秀优秀判定树判定树 第5页/共21页第六页，共21页。按图的判定按图的判定(pndng)过程过程:转换一个分数所需的比较次数转换一个分数所需的比较次数=从根到对应结点的路径长度从根到对应结点的路径长度转换转换10000个分数所需的个分数所需的总比较次数总比较次数=10000 (0.05 1+0.15 2+0.4 3+0.3 4+0.1 4）二叉树的二叉树的带权路径带权路径(ljng)长度长度优秀优秀a a 80 80a a 90 90不及格不及格良好良好中等中等及格及格a a 60 60a a 70 70分数分数 0-59 60-69 70-79 80-89 90-1000-59 60-69 70-79 80-89 90-100比例数比例数0.05 0.15 0.40 0.30 0.100.05 0.15 0.40 0.30 0.10 设有设有10000个百分制分数个百分制分数(fnsh)要转换，设学生成绩在要转换，设学生成绩在5个等个等级以上的分布如下：级以上的分布如下：构造以分数的分布比例为权值构造以分数的分布比例为权值的哈夫曼树的哈夫曼树第6页/共21页第七页，共21页。3哈夫曼树的构造哈夫曼树的构造(guzo)假假设设有有n个个权权值值，则则构构造造(guzo)出出的的哈哈夫夫曼曼树树有有n个个叶叶子子结结点点。n个权值分别设为个权值分别设为 w1,w2,wn,则哈夫曼树的构造则哈夫曼树的构造(guzo)规则为：规则为：(1)将将w1,w2,wn看看成成(kn chn)是是有有n 棵棵树树的的森森林林(每每棵棵树树仅仅有有一一个结点个结点)；(2)在森林中选出两个根结点在森林中选出两个根结点(ji din)的权值最小的树合并，作的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点为一棵新树的左、右子树，且新树的根结点(ji din)权值为其左、权值为其左、右子树根结点右子树根结点(ji din)权值之和；权值之和；(3)从森林中删除选取的两棵树，并将新树加入森林；从森林中删除选取的两棵树，并将新树加入森林；(4)重复重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为我们步，直到森林中只剩一棵树为止，该树即为我们所求得的哈夫曼树。所求得的哈夫曼树。构造哈夫曼树的模拟演示构造哈夫曼树的模拟演示第7页/共21页第八页，共21页。下下面面给给出出哈哈夫夫曼曼树树的的构构造造过过程程，假假设设给给定定的的叶叶子子结结点点(ji din)的的权分别为权分别为1,5,7,3，则构造哈夫曼树过程如图所示。，则构造哈夫曼树过程如图所示。第8页/共21页第九页，共21页。n 个权值构造哈夫曼树需个权值构造哈夫曼树需n-1次合并次合并(hbng)，每次合，每次合并并(hbng)，森林中的树数目减，森林中的树数目减1，最后森林中只剩下，最后森林中只剩下一棵树，即为我们求得的哈夫曼树。一棵树，即为我们求得的哈夫曼树。例：例：W（权）（权）=2,4,2,3,3，叶子，叶子(y zi)结点个数结点个数m=5试设计试设计Huffman树。树。哈夫曼树的算法模拟演示哈夫曼树的算法模拟演示第9页/共21页第十页，共21页。3 3、哈夫曼树构造程序、哈夫曼树构造程序 一棵有n个叶子(y zi)结点的Huffman树有2n-1个结点顺序存储结构一维结构数组存储结点信息，结点类型定义为：typedef struct int weight;int parent,lchild,rchild;JD;#define MAX 100void huffman(int n,int w,JD t)int i,j,k,x1,x2,m1,m2;for(i=1;i(2*n);i+)ti.parent=ti.lchild=ti.rchild=-1;if(i=n)ti.weight=wi;else ti.weight=0;第10页/共21页第十一页，共21页。for(i=1;in;i+)m1=m2=MAX;x1=x2=0;for(j=1;j(n+i);j+)if(tj.weightm1)&(tj.parent=-1)m2=m1;x2=x1;m1=tj.weight;x1=j;else if(tj.weightm2)&(tj.parent=-1)m2=tj.weight;x2=j;k=n+i;tx1.parent=tx2.parent=k;tk.weight=m1+m2;tk.lchild=x1;tk.rchild=x2;第11页/共21页第十二页，共21页。例：例：W（权）（权）=2,4,2,3,3，叶子，叶子(y zi)结点个数结点个数,m=5试设计试设计Huffman树。树。1484642233构造的构造的Huffman树树 第12页/共21页第十三页，共21页。在远程通讯在远程通讯(tngxn)中，要将待传字符转换成由二进中，要将待传字符转换成由二进制组成的字符串：制组成的字符串：设要传送的字符为：设要传送的字符为：ABACCDA若编码为：若编码为：A00(等长等长)B01 C10 D-11 若将编码若将编码(bin m)设计为长度不等的二进制编码设计为长度不等的二进制编码(bin m)，即，即让待传字符串中出现次数较多的字符采用尽可能短的编码让待传字符串中出现次数较多的字符采用尽可能短的编码(bin m)，则转换的二进制字符串便可能减少。，则转换的二进制字符串便可能减少。三、哈夫曼树的应用三、哈夫曼树的应用(yngyng)(哈夫曼编码哈夫曼编码)第13页/共21页第十四页，共21页。设要传送设要传送(chun sn)的字符为：的字符为：ABACCDA若编码为：若编码为：A0 B00 C1 D-01 关键：要设计长度不等的编码，则必须使任一字符关键：要设计长度不等的编码，则必须使任一字符(z f)的编码都不的编码都不是另一个字符是另一个字符(z f)的编码的前缀。这种编码称作最优前缀编码。的编码的前缀。这种编码称作最优前缀编码。ABACCDA 000011010但：但：0000AAAA ABA BB重码重码(zhn m)第14页/共21页第十五页，共21页。0设要传送的字符设要传送的字符(z f)为：为：ABACCDA若编码为若编码为：A0 B110 C10 D-111 ACBD00111采用采用(ciyng)二二叉树设计二进叉树设计二进制前缀编码制前缀编码规定规定(gudng)：左分支用左分支用“0”表示表示右分支用右分支用“1”表示表示第15页/共21页第十六页，共21页。译码过程：分解接收字符译码过程：分解接收字符(z f)串：遇串：遇“0”向左，向左，遇遇“1”向右；一旦到达叶子结点，则译出一个字符向右；一旦到达叶子结点，则译出一个字符(z f)，反复由根出发，直到译码完成。，反复由根出发，直到译码完成。ABACCDAA0 B110C10D-111ACBD000111第16页/共21页第十七页，共21页。例：已知某系统在通讯时，只出现例：已知某系统在通讯时，只出现C，A，S，T，B五种字符，它们出现的频率依次为五种字符，它们出现的频率依次为2，4，2，3，3，试设计试设计Huffman编码编码(bin m)。W（权）（权）=2，4，2，3，3，叶子结点个数，叶子结点个数m=5 148464220001113301构造的构造的Huffman树树 T B A C S第17页/共21页第十八页，共21页。例：已知某系统在通讯时，只出现例：已知某系统在通讯时，只出现C，A，S，T，B五五种字符，它们出现的频率种字符，它们出现的频率(pnl)依次为依次为2，4，2，3，3，试设计，试设计Huffman编码。编码。由由Huffman树得树得Huffman编码为：编码为：T B A C S00 01 10 110 111出现出现(chxin)频率频率越大的字符，其越大的字符，其Huffman编码越短。编码越短。148464220001113301 T B A C S第18页/共21页第十九页，共21页。可利用二叉树设计前缀可利用二叉树设计前缀(qinzhu)编编码：码：例例 某通讯系统只使用某通讯系统只使用8种字符种字符a、b、c、d、e、f、g、h，其使，其使用频率分别为用频率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，利用，利用二叉树设计一种不等长编码：二叉树设计一种不等长编码：1）构造）构造(guzo)以以 a、b、c、d、e、f、g、h为叶子结点的二为叶子结点的二叉树；叉树；2）将该二叉树所有左分枝标记）将该二叉树所有左分枝标记0，所有右分枝标记，所有右分枝标记1；3）从根到叶子结点路径上标记作为叶子结点所对应字符的编）从根到叶子结点路径上标记作为叶子结点所对应字符的编码；码；第19页/共21页第二十页，共21页。a:0001a:0001b:10b:10c:1110c:1110d:1111d:1111e:110e:110f:01f:01g:0000g:0000h:001h:00129295858424210010015157 78 8232314142929191911118 85 53 3构造以字符构造以字符(z f)使用频率使用频率作为权值的哈夫曼树作为权值的哈夫曼树如何得到使二进如何得到使二进制串总长最短编制串总长最短编码码0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11第20页/共21页第二十一页，共21页。
