第六章树与二叉树6赫夫曼树及其应用.ppt

1、6.1 树的定义和基本术语,第六章 树和二叉树,6.2 二叉树,6.3 遍历二叉树和线索二叉树,6.5 赫夫曼树及其应用,6.4 树和森林,6.5 赫夫曼树及其应用,编制一个将学生的百分制成绩转换成五分制成绩的程序。其中若成绩低于60分，记为“bad”;成绩介于60和69之间，记为“pass”;成绩介于70和79之间的，记为“general”;成绩介于80和89之间的，记为“good”;成绩高于90分的，记为“excellent”。,if (a60) score=“bad”; else if(a70) score=“pass”; else if(a80) score=“general”; el

2、se if(a90) score=“good”; else score=“excellent”;,10000(10.05+20.15+30.4+40.4) =31500,10000(20.4+20.3+20.1+30.2) =22000,一. 概念,路径上的分支数目称为路径长度；,路径,从树中一个结点到另一个结点之间的分支构成这两个结点间的路径；,路径长度,树的路径长度,从树根到树中其余每个结点的路径长度之和。,6.5 赫夫曼树及其应用,从根到该结点的路径长度与该结点权值的乘积；,结点的权,根据需要给结点所赋的值；,结点的带权路径长度,5,2,6,3,一. 概念,6.5 赫夫曼树及其应用,树的

3、带权 路径长度,树中所有叶子结点的带权路径长度之和。记作:,一. 概念,6.5 赫夫曼树及其应用,WPL=,其中， Wk代表第k个叶子的权值；,lk代表从根结点到第k个叶子的路径长度。,5,2,6,3,树的带权路径长度,WPL=14+10+4+8=36,WPL=8+21+15+2=46,WPL=7+10+6+12=35,一. 概念,6.5 赫夫曼树及其应用,最优二叉树(Huffman树),即假设有n个权值(w1 ,w2 , , wn )，构造有一棵n个叶子结点的二叉树，每个叶子结点带权值wi 。则带权路径长度WPL最小的二叉树称为最优二叉树，又称为赫夫曼树。,一. 概念,6.5 赫夫曼树及其应

4、用,最优二叉树的特点,一. 概念,6.5 赫夫曼树及其应用,权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。 2. 只有度为0（叶子结点） 和度为2（分支结点）的 结点，不存在度为1的结 点。,二.最优二叉树的构造,1初始化：根据给定的n个权值 ，构造n棵二叉树集合 F，其中每棵二叉树中只有一个带权为wi的根结点， 其左右子树均为空； 2选取与合并：在F中选取两棵根结点权值最小的树作 为左、右子树，构造一棵新的二叉树，且置新二叉树 根的权值为左、右子树根结点权值之和； 3删除与加入：从F中删除这两棵树，并将新树加入F； 4重复 2、3，直到F中只含一棵树为止。这棵树就是所 求

5、的赫夫曼树。,赫夫曼算法步骤：,6.5 赫夫曼树及其应用,第1步：初始化,举例：W2，4，5，3 赫夫曼树的构造过程,第2步：选取与合并,第3步：删除与加入,6.5 赫夫曼树及其应用,重复第2步,5,4,3,2,5,重复第3步,6.5 赫夫曼树及其应用,举例：W2，4，5，3 赫夫曼树的构造过程,重复第2步,重复第3步,6.5 赫夫曼树及其应用,举例：W2，4，5，3 赫夫曼树的构造过程,练习：构造以W=（5，4，7，2，5）为权的赫夫曼树。,最优二叉树的左右子树可以互换； 结点权值差别很大时，构成如图所示形状； 所有结点权值一样时，构成完全二叉树形状；,说明,最优二叉树结点数为叶子数的2倍减

6、1。,说明,证明： 由二叉树性质3得： n0=n2+1 故最优二叉树结点数=n0+n2=n0+n0-1=2n0-1,赫夫曼树的存储,weight parent lchild rchild,权值,双亲,左孩子,右孩子,typedef struct int weight; int parent, lchild, rchild; HTNode, *HuffmanTree; /动态分配数组存储赫夫曼树,6.5 赫夫曼树及其应用,void HuffmanTree(HuffmanTree ,赫夫曼树的构造算法,例：构造以W=(5,29,7,8,14,23,3,11)为权的赫夫曼树。, if (n=1) r

7、eturn; /n=8个叶子结点 m=2* n-1; /m=2n-1=15 HT=(HuffmanTree)malloc (m+1) * sizeof(HTNode); for (p=HT+1, i=1; i=n; +i, +p, +w) * p= * w, 0, 0, 0; for (; i=m; +i, +p) * p= 0, 0, 0, 0; ,HT,例：构造以W=(5,29,7,8,14,23,3,11)为权的赫夫曼树。, for (i=n+1; i=m; +i) Select(HT, i-1, s1, s2); /在HT1.i-1 选择parent为0 且weight最小的两个结点，

8、其 序号分别为s1和s2 HTs1. parent =i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight +HTs2.weight; ,HT,5,3,9,9,1,7,8,7,8,10,10,3,4,15,例：构造以W=(5,29,7,8,14,23,3,11)为权的赫夫曼树。,HT,147页,三.赫夫曼编码,编码：用不同的0、1序列代表不同的信息。 等长编码 不等长编码,如：ASCII码长为8，字符A、B、Z分别表示为 A 01000001 B 01000010 Z 01011010,6.5 赫夫曼树及其

9、应用,例：在远程通讯中，要将待传字符转换成由二进制组成的字符串： 设要传送的字符为： ABACCDA 若编码为：A00 B01 C10 D-11,若将编码设计为长度不等的二进制编码，即让待传字符串中出现次数较多的字符采用尽可能短的编码，则转换的二进制字符串便可能减少。,00010010101100,6.5 赫夫曼树及其应用,三.赫夫曼编码,例：在远程通讯中，要将待传字符转换成由二进制组成的字符串： 设要传送的字符为： ABACCDA 若编码为：A0 B00 C1 D-01,关键：要设计长度不等的编码，则必须使任一字符的编码都不是另一个字符的编码的前缀。这种编码称作前缀编码。,000011010,6.5 赫夫曼树及其应用,三.赫夫曼编码,0000 AAAA ABA BB,重码,例：在远程通讯中，要将待传字符转换成由二进制组成的字符串： 设要传送的字符为： ABACCDA 若编码为：A0 B110 C10 D-111,采用二叉树设计二进制前缀编码,规定：左分支用“0”表示；右分支用“1”表示。,0110010101110,6.5 赫夫曼树及其应用,三.赫夫曼编码,三.赫夫曼编码,例：某通讯系统只使用8种字符a、b、c、d、e、f、g、h， 其使用频率分别为0.05,0.29,0.07,0.08,0.