数据结构哈夫曼树.pptx

1 1路径和路径长度路径和路径长度在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。6.6 6.6 哈夫曼树哈夫曼树一、基本术语基本术语ABCDEFG第1页/共21页2 2结点的权及带权路径长度结点的权及带权路径长度给树的结点附加的这个有着某种意义的实数，称为该结点的权（weight）。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。ABCDEFG412537第2页/共21页3树的带权路径长度树的带权路径长度树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为wpl=其中n 为叶子结点数目，wi为第i 个叶子结点的权值，li 为第i 个叶子结点的路径长度。二、构造哈夫曼树二、构造哈夫曼树1哈夫曼树的定义哈夫曼树的定义在一棵二叉树中，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。第3页/共21页例 有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=35要使二叉树WPL小,就须在构造树时,将权值大的结点靠近根.第4页/共21页2 2 应用举例应用举例在求得某些判定问题时，利用哈夫曼树获得最佳判定算法。例 编制一个将百分制转换成五分制的程序。最直观的方法是利用if语句来的实现。if(x60)score=不及格;else if(x70)score=及格;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页按图的判定过程:转换一个分数所需的比较次数=从根到对应结点的路径长度转换10000个分数所需的总比较次数=10000 (0.05 1+0.15 2+0.4 3+0.3 4+0.1 4）二叉树的带权路径长度优秀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个百分制分数要转换，设学生成绩在5个等级以上的分布如下：构造以分数的分布比例为权值的哈夫曼树第6页/共21页3哈夫曼树的构造哈夫曼树的构造假设有n个权值，则构造出的哈夫曼树有n个叶子结点。n个权值分别设为 w1,w2,wn,则哈夫曼树的构造规则为：(1)将w1,w2,wn看成是有n 棵树的森林(每棵树仅有一个结点)；(2)在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；(3)从森林中删除选取的两棵树，并将新树加入森林；(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为我们所求得的哈夫曼树。构造哈夫曼树的模拟演示第7页/共21页下面给出哈夫曼树的构造过程，假设给定的叶子结点的权分别为1,5,7,3，则构造哈夫曼树过程如图所示。第8页/共21页n 个权值构造哈夫曼树需n-1次合并，每次合并，森林中的树数目减1，最后森林中只剩下一棵树，即为我们求得的哈夫曼树。例：W（权）=2,4,2,3,3，叶子结点个数m=5试设计Huffman树。哈夫曼树的算法模拟演示第9页/共21页3 3、哈夫曼树构造程序、哈夫曼树构造程序 一棵有n个叶子结点的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页 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页例：W（权）=2,4,2,3,3，叶子结点个数,m=5试设计Huffman树。1484642233构造的Huffman树 第12页/共21页 在远程通讯中，要将待传字符转换成由二进制组成的字符串：设要传送的字符为：ABACCDA若编码为：A00(等长)B01 C10 D-11 若将编码设计为长度不等的二进制编码，即让待传字符串中出现次数较多的字符采用尽可能短的编码，则转换的二进制字符串便可能减少。三、哈夫曼树的应用(哈夫曼编码哈夫曼编码)第13页/共21页设要传送的字符为：ABACCDA若编码为：A0 B00 C1 D-01 关键：要设计长度不等的编码，则必须使任一字符的编码都不是另一个字符的编码的前缀。这种编码称作最优前缀编码。ABACCDA 000011010但：0000AAAA ABA BB重码第14页/共21页0设要传送的字符为：ABACCDA若编码为：A0 B110 C10 D-111 ACBD00111采用二叉树设计二进制前缀编码规定：左分支用“0”表示右分支用“1”表示第15页/共21页译码过程：分解接收字符串：遇“0”向左，遇“1”向右；一旦到达叶子结点，则译出一个字符，反复由根出发，直到译码完成。ABACCDAA0 B110C10D-111ACBD000111第16页/共21页例：已知某系统在通讯时，只出现C，A，S，T，B五种字符，它们出现的频率依次为2，4，2，3，3，试设计Huffman编码。W（权）=2，4，2，3，3，叶子结点个数m=5 148464220001113301构造的Huffman树 T B A C S第17页/共21页例：已知某系统在通讯时，只出现C，A，S，T，B五种字符，它们出现的频率依次为2，4，2，3，3，试设计Huffman编码。由Huffman树得Huffman编码为：T B A C S00 01 10 110 111出现频率越大的字符，其Huffman编码越短。148464220001113301 T B A C S第18页/共21页可利用二叉树设计前缀编码：可利用二叉树设计前缀编码：例 某通讯系统只使用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）构造以 a、b、c、d、e、f、g、h为叶子结点的二叉树；2）将该二叉树所有左分枝标记0，所有右分枝标记1；3）从根到叶子结点路径上标记作为叶子结点所对应字符的编码；第19页/共21页a:0001a:0001b:10b:10c:1110c:1110d:1111d:1111e:110e:110f:01f:01g:0000g:0000h:001h:00129295858424210010015157 78 8232314142929191911118 85 53 3构造以字符使用频率作为权值的哈夫曼树如何得到使二进制串总长最短编码0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11第20页/共21页感谢您的观看！第21页/共21页