最优二叉树哈夫曼树

1、最优二叉树哈夫曼树【重点与难点】1. 带权二叉树与哈夫曼树基本概念；2. 构造哈夫曼树；3. 哈夫曼编码及其算法实现。【引入】在实际应用中，常常要考虑一个问题：如何设计一棵二叉树，使得执行路径最短，即 算法的效率最高。例快递包裹的邮资问题假设邮政局的包裹自动测试系统能够测出包裹的重量，如何设计一棵二叉树将包裹根 据重量及运距进行分类从而确定邮资。国内快递包裹资费 单位：元（2004年1月1日起执行）运距（公里）首重1000克5000克以内续重每500克5001克以上续重每500克<=500<=1000>500<=1500>1000<=2000>1500

2、<=2500>2000<=3000>2500<=4000>3000<=5000>4000<=6000>5000>6000表7.1国家邮政局制定的快递包裹参考标准根据表可以制定出许多种二叉树，但不同的二叉树判定的次数可能不一样，执行的效 率也不同。例7.2铁球分类现有一批球磨机上的铁球，需要将它分成四类：直径不大于20的属于第一类；直径大于20而不大于50的属于第二类；直径大于50而不大于100的属于第三类；其余的属于 第四类；假定这批球中属于第一、二、三、四类铁球的个数之比例是123:4。我们可以把这个判断过程表示为图中的两种方

3、法：图7.1两种判断二叉树示意图那么究竟将这个判断过程表示成哪一个判断框，才能使其执行时间最短呢？让我们对上述判断框做一具体的分析。假设有1000个铁球，则各类铁球的个数分别为：100、200、300、400 ；左图序号比较式比较次数1a<=2010002a<=509003a<=100700合计2600右图序号比较式比较次数1a>10010002a>506003a<=20300合计1900表两种判断二叉树比较次数过上述分析可知，图中右图所示的判断框的比较次数远远小于左图所示的判断框的比较次数。为了找出比较次数最少的判断框，将涉及到树的路径长度问题。哈夫曼树的

4、基本概念最优二叉树，也称哈夫曼（Hafman ）树，是指对于一组带有确定权值的叶结点，构 造的具有最小带权路径长度的二叉树。那么什么是二叉树的带权路径长度呢？在前面我们介绍过路径和结点的路径长度的概念，而二叉树的路径长度则是指由根结 点到所有叶结点的路径长度之和。如果二叉树中的叶结点都具有一定的权值，则可将这一 概念加以推广。设二叉树具有 n个带权值的叶结点，那么从根结点到各个叶结点的路径长 度与相应结点权值的乘积之和叫做二叉树的带权路径长度，记为：n刀WPL = k=1 Wk k其中Wk为第k个叶结点的权值，Lk为第k个叶结点的路径长度。如图 7.2所示的二叉树，它的带权路径长度值 WPL

5、= 2 X2 + 4 X2 + 5 X2 + 3 X2 = 28。在给定一组具有确定权值的叶结点，可以构造出不同的带权二叉树。例如，给出4个叶结点，设其权值分别为 1 , 3 , 5 , 7,我们可以构造出形状不同的多个二叉树。这些形状不同的二叉树的带权路径长度将各不相同。图7.3给出了其中5个不同形状的二叉树。这五棵树的带权路径长度分别为:(a) WPL = 1 X2 + 3 X2 + 5X2 + 7 X2 = 32(b ) WPL = 1 X3 + 3 X3 + 5 X2 + 7 X1 = 29(c) WPL = 1 X2 + 3 X3 + 5X3 + 7 X1 = 33(d ) WPL

6、= 7 X3 + 5X3 + 3 X2 + 1 X1 = 43图7.2一个带权二叉树(e) WPL = 7 X1 + 5X2 + 3X3 + 1 X3 = 29(d)(e)图7.3具有相同叶子结点和不同带权路径长度的二叉树由此可见，由相同权值的一组叶子结点所构成的二叉树有不同的形态和不同的带权路 径长度，那么如何找到带权路径长度最小的二叉树（即哈夫曼树）呢？根据哈夫曼树的定义，一棵二叉树要使其 WPL值最小，必须使权值越大的叶结点越靠近根结点，而权值越 小的叶结点越远离根结点。哈夫曼(Haffman )依据这一特点于1952年提出了一种方法，这种方法的基本思想 是：(1 )由给定的n个权值W1

7、 , W2，Wn构造n棵只有一个叶结点的二叉树，丿 而得到一个二叉树的集合 F= T1, T2,，Tn;(2 )在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新 的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和；(3) 在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集 合F中；(4) 重复(2) ( 3)两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的 哈夫曼树。由于这种算法是哈夫曼最早提出的，所以将最优二叉树称为哈夫曼树。图给出了前面提到的叶结点权值集合为W = 1 , 3 , 5 , 7的哈夫曼树的构造过程。以计算出其带权路径

8、长度为29 ,由此可见，对于同一组给定叶结点所构造的哈夫曼树，第四步第二步716的形状可能不同，但带权路径长度值是相同的，一定是最小的。7;5；3' U第三步;941图7.4哈夫曼树的建立过程7.2哈夫曼树的构造算法从上述算法中可以看出，F实际上是森林，该算法的思想是不断地进行森林F中的二叉树的“合并”，最终得到哈夫曼树。在构造哈夫曼树时，可以设置一个结构数组HufNode 保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有 2n -1个结点，所以数组HuffNode 的大小设置为2n 1,数组元素的结构形式如下:weightlchildpare nt其中

9、，weightrchild域保存结点的权值,存该结点的左、右孩子结点在数组HuffNode中的序号，从而建立起结点之间的关系。为了判定一个结点是否已 加入到要建立的哈夫曼树中，可通过 pare nt域的值来确定。初始时 parent的值为1 ,当结点加入到树中时，该结点parent的值为其双亲结点在数组HuffNode中的序号，就不会是1 了。构造哈夫曼树时，首先将由n个字符形成的n个叶结点存放到数组 HuffNode 的前n个分量中，然后根据前面介绍的哈夫曼方法的基本思想，不断将两个小子树合并为一个较大的子树，每次构成的新子树的根结点顺序放到HufNode 数组中的前n个分量的后面。F面给出

10、哈夫曼树的构造算法。constmaxvalue= 10000; 定义最大权值 maxleat=30; 定义哈夫曼树中叶子结点个数 maxnode=maxleaf*2-1;type HnodeType=recordweight: integer;parent: integer;lchild: integer;rchild: integer;end;HuffArr:array0.maxnode of HnodeType;var 哈夫曼树的构造算法 procedure CreatHaffmanTree(var HuffNode: HuffArr); var i,j,m1,m2,x1,x2,n: in

11、teger;beginreadln(n); 输入叶子结点个数 for i:=0 to 2*n-1 do 数组 HuffNode 初始化 beginHuffNodei.weight=0;HuffNodei.parent=-1;HuffNodei.lchild=-1;HuffNodei.rchild=-1;end;for i:=0 to n-1 do read(HuffNodei.weight); 输入 n 个叶子结点的权值 for i:=0 to n-1do 构造哈夫曼树 beginm1:=MAXVALUE;m2:=MAXVALUE;x1:=0; x2:=0;for j:=0 to n+i-1

12、doif (HuffNodej.weight<m1) and (HuffNodej.parent=-1) thenbegin m2:=m1; x2:=x1;m1:=HuffNodej.weight; x1:=j;endelse if (HuffNodej.weight<m2) and (HuffNodej.parent=-1) thenbegin m2:=HuffNodej.weight; x2:=j; end;将找出的两棵子树合并为一棵子树 HuffNodex1.parent:=n+i; HuffNodex2.parent:=n+i;HuffNoden+i.weight:= Hu

13、ffNodex1.weight+HuffNodex2.weight;HuffNoden+i.lchild:=x1;HuffNoden+i.rchild:=x2;end;end;7.3哈夫曼树在编码问题中的应用表c表d字符编码A000Ad AB0 10C100D111字符编码A0(B0字符编码AB字符编码B-010C10C10C001D11D111D10表字符的四种不同的编码方案哈夫曼树可用于构造使电文的编码总长最短的编码方案。具体做法如下：设需要编码的字符集合为d1，d2，dn,它们在电文中出现的次数或频率集合为 w1 , w2，, wn，以d1 , d2，dn作为叶结点，w1 , w2，wn

14、作为它们的权值，构造一棵哈 夫曼树，规定哈夫曼树中的左分支代表0,右分支代表1，则从根结点到每个叶结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，我们称之为哈夫曼编码。在哈夫曼编码树中，树的带权路径长度的含义是各个字符的码长与其出现次数的乘积之和，也就是电文的代码总长，所以采用哈夫曼树构造的编码是一种能使电文代码总长最 短的不等长编码。在建立不等长编码时，必须使任何一个字符的编码都不是另一个字符编码的前缀，这样才能保证译码的唯一性。例如表（d）的编码方案，字符A的编码01是字符B的编码010 的前缀部分，这样对于代码串 0101001，既是AAC的代码，也是 ABD和BDA的代

15、码， 因此，这样的编码不能保证译码的唯一性，我们称之为具有二义性的译码。然而，采用哈夫曼树进行编码，则不会产生上述二义性问题。因为，在哈夫曼树中，每个字符结点都是叶结点，它们不可能在根结点到其它字符结点的路径上，所以一个字符的哈夫曼编码不可能是另一个字符的哈夫曼编码的前缀，从而保证了译码的非二义性。下面讨论实现哈夫曼编码的算法。实现哈夫曼编码的算法可分为两大部分：（1 ）构造哈夫曼树；（2）在哈夫曼树上求叶结点的编码。求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶结点开始，沿结点的双亲链域回退到根结点，每回退一步，就走过了哈夫曼树的一个分支， 从而得到一位哈夫曼码值， 由于一个字符的哈夫曼

16、编码是从根结点到相应叶结点所经过的路径上各分支所组成的0，1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求编码的高位 码。我们可以设置一结构数组 HufCode用来存放各字符的哈夫曼编码信息，数组元素的结构如下:其中，分量bitbitstart维数组，用来保存字符的哈夫曼编码,start表示该编码在数组bit中的开始位置。所以，对于第i个字符，它的哈夫曼编码存放在HuffCodei.bit 中的从 HuffCodei.start至U n 的分量上。【求哈夫曼编码程序段】const Maxleaf=128;定义最多叶结点数 MaxNode=255;定义最大结点数 MaxBi

17、t=10; 定义哈夫曼编码的最大长度 type HCodeType =record bit: array0.MaxBit ofinteger;start: integer;end;procedure HaffmanCode ;生成哈夫曼编码 var HuffNode: array0.MaxNode of HCodeType;HuffCode: array0.MaxLeaf of HcodeType;cd : HcodeType;i,j, c,p: integer ;beginHuffmanTree (HuffNode ); 建立哈夫曼树 for i:=0 to n-1 do 求每个叶子结点的哈

18、夫曼编码 begin:=n-1; c:=i;p:=HuffNodec.parent;whilep<>0 do 由叶结点向上直到树根 ifHuffNodep.lchild=c then cd.bitcd.start:=0else cd.bitcd.start:=1;dec ();c:=p;p:=HuffNodec.parent;end;for j:=cd.start+1 to n-1do 保存求出的每个叶结点的哈夫曼编码和编码的起始位 beginHuffCodei.bitj:=cd.bitj;HuffCodei.start=cd.start;end;fori:=0 to n-1 do

19、 输出每个叶子结点的哈夫曼编码 beginfor j:=HuffCodei.start+1 to n-1 dowrite(HuffCodei.bitj:10);writeln;end;end;7.4 文件的编码和解码通过从上一节的学习，我们知道了如何利用哈夫曼树来构造字符编码。有了字符集的哈夫曼编码表之后，对数据文件的编码过程是：依次读人文件中的字符C,在哈夫曼编码表 H 中找到此字符，若 Hi.ch=c ，则将字符 c 转换为 Hi.bits 中存放的编码串。对压缩后的数据文件进行解码则必须借助于哈夫曼树 T,其过程是：依次读人文件的 二进制码，从哈夫曼树的根结点 （即 Tm-1） 出发，若

20、当前读人 0，则走向左孩子，否则走 向右孩子。一旦到达某一叶子 Ti时便译出相应的字符 Hi.ch。然后重新从根出发继续译 码，直至文件结束。哈夫曼树在判定问题中的应用在本章的引入部分，两个例子都是判定问题，这两个判定问题都可以通过构造哈夫曼 树来优化判定，以达到总的判定次数最少。再如，要编制一个将百分制转换为五级分制的程序。显然，此程序很简单，只要利用 条件语句便可完成。【程序段】if a<60 then b:='bad 'else if a<70 then b:=' pass'else ifa<80 then b:='general

21、 'else if a<90 then b:='good 'else b:= ' excellent如果上述程序需反复使用，而且每次的输入量很大，则应考虑上述程序的质量问题，即其操作所需要的时间。因为在实际中，学生的成绩在五个等级上的分布是不均匀的，假 设其分布规律如表所示：分数0 5960 6970 7980 8990 100表分数段的分布频率则80 %以上的数据需进行三次或三次以上的比较才能得出结果。假定以5 ,15 , 40, 30和10为权构造一棵有五个叶子结点的哈夫曼树，它可使大部分的数据经过较少的比较次数得出结果。但由于每个判定框都有两次比较，将这两次比较分开，得到新的判定树，按 此判定树可写出相应的程序。请您自己画出此判定树。假设有10000个输入数据，若上程序段的判定过程进行操作，则总共需进行31500次比较；而若新判定树的判定过程进行操作，则总共仅需进行22000次比较。习题解答题1. 证明：在结点数大于1的哈夫曼树中不存在度为1的结点。2. 假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为 7、19、2、6、32、3、21、10。试为这8个字母设计哈夫曼编码。如果用 07这8个 数的二进制数表示这 8 个字母也是一种编码方案，试比较这两种方法的优劣。3 有 7 个带权结点 a,b,c,