《最优二叉树哈夫曼树》由会员分享，可在线阅读，更多相关《最优二叉树哈夫曼树（10页珍藏版）》请在金锄头文库上搜索。
1、最优二叉树哈夫曼树【重点与难点】1. 带权二叉树与哈夫曼树基本概念；2. 构造哈夫曼树；3. 哈夫曼编码及其算法实现。【引入】在实际应用中，常常要考虑一个问题：如何设计一棵二叉树，使得执行路径最短，即 算法的效率最高。例7.1快递包裹的邮资问题假设邮政局的包裹自动测试系统能够测出包裹的重量，如何设计一棵二叉树将包裹根 据重量及运距进行分类从而确定邮资。国内快递包裹资费 单位：元 （2004年1月1日起执行）运距（公里）首重1000克5000克以内续重每500克5001克以上续重每500克=5005.002.001.005006.002.501.3010007.003.001.6015008.0
2、03.501.9020009.004.002.20250010.004.502.50300012.005.503.10400014.006.503.70500016.007.504.30600020.009.006.00表7.1国家邮政局制定的快递包裹参考标准根据表7.1可以制定出许多种二叉树，但不同的二叉树判定的次数可能不一样，执行 的效率也不同。例7.2铁球分类现有一批球磨机上的铁球，需要将它分成四类：直径不大于20的属于第一类；直径大于20而不大于50的属于第二类；直径大于50而不大于100的属于第三类；其余的属于第 四类；假定这批球中属于第一、二、三、四类铁球的个数之比例是123:4
3、。我们可以把这个判断过程表示为图7.1中的两种方法：图7.1两种判断二叉树示意图那么究竟将这个判断过程表示成哪一个判断框，才能使其执行时间最短呢？让我们对 上述判断框做一具体的分析。假设有1000个铁球，则各类铁球的个数分别为：100、200、300、400;对于图7.1中的左图和右图比较的次数分别如表7.2所示：左图序号比较式比较次数1a=2010002a=509003a10010002a506003a=20300合计1900表7.2两种判断二叉树比较次数过上述分析可知，图7.1中右图所示的判断框的比较次数远远小于左图所示的判断框 的比较次数。为了找出比较次数最少的判断框，将涉及到树的路径长
4、度问题。7.1哈夫曼树的基本概念最优二叉树，也称哈夫曼（Hafman ）树，是指对于一组带有确定权值的叶结点，构 造的具有最小带权路径长度的二叉树。那么什么是二叉树的带权路径长度呢？在前面我们介绍过路径和结点的路径长度的概念，而二叉树的路径长度则是指由根结 点到所有叶结点的路径长度之和。如果二叉树中的叶结点都具有一定的权值，则可将这一 概念加以推广。设二叉树具有 n个带权值的叶结点，那么从根结点到各个叶结点的路径长 度与相应结点权值的乘积之和叫做二叉树的带权路径长度，记为：nWPL =刀 Wk Lk其中Wk为第k个叶结点的权值，Lk为第k个叶结点的路径长度。如图 7.2所示的二 叉树，它的带权
5、路径长度值 WPL = 2X 2 + 4X 2+ 5 X 2+ 3X 2= 28。在给定一组具有确定权值的叶结点，可以构造出不同的带权二叉树。例如，给出4个叶结点，设其权值分别为1, 3, 5, 7,我们可以构造出形状不同的多个二叉树。这些形状 不同的二叉树的带权路径长度将各不相同。图7.3给出了其中5个不同形状的二叉树。这五棵树的带权路径长度分别为：(a) WPL = 1 X 2+ 3X 2 + 5X 2 + 7X 2= 32(b) WPL = 1 X 3+ 3X 3 + 5X 2+ 7X 1 = 29(c) WPL = 1 X 2+ 3X 3 + 5X 3 + 7X 1 = 33(d) W
6、PL = 7X 3+ 5X 3 + 3X 2+ 1 X 1 = 43图7.3具有相同叶子结点和不同带权路径长度的二叉树(e) WPL = 7X 1 + 5X 2 + 3X 3+ 1 X 3= 29由此可见，由相同权值的一组叶子结点所构成的二叉树有不同的形态和不同的带权路 径长度，那么如何找到带权路径长度最小的二叉树(即哈夫曼树)呢？根据哈夫曼树的定 义，一棵二叉树要使其 WPL值最小，必须使权值越大的叶结点越靠近根结点，而权值越 小的叶结点越远离根结点。哈夫曼(Hafman )依据这一特点于1952年提出了一种方法，这种方法的基本思想是: (1 )由给定的n个权值W1 , W2 ,，Wn构造n
7、棵只有一个叶结点的二叉树，从 而得到一个二叉树的集合 F=T1 , T2,，Tn;(2 )在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新 的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和；(3) 在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集 合F中；(4) 重复(2) ( 3)两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。由于这种算法是哈夫曼最早提出的，所以将最优二叉树称为哈夫曼树。图7.4给出了前面提到的叶结点权值集合为 W = 1 , 3, 5, 7的哈夫曼树的构造过程。 可以计算出其带权路径长度为 29,由
8、此可见，对于同一组给定叶结点所构造的哈夫曼树， 树的形状可能不同，但带权路径长度值是相同的，一定是最小的。第一步7. 2哈夫曼树的构造算法从上述算法中可以看出，F实际上是森林，该算法的思想是不断地进行森林F中的二叉树的“合并”，最终得到哈夫曼树。在构造哈夫曼树时，可以设置一个结构数组 HufNode保存哈夫曼树中各结点的信息， 根据二叉树的性质可知，具有 n个叶子结点的哈夫曼树共有 2n-1个结点，所以数组 HuffNode的大小设置为2n 1,数组元素的结构形式如下：weightlchildrchildpare nt其中，weight域保存结点的权值，Ichild和rchild域分别保存该结
9、点的左、右孩子结点在数组HuffNode中的序号，从而建立起结点之间的关系。为了判定一个结点是否已加入 到要建立的哈夫曼树中， 可通过pare nt域的值来确定。初始时pare nt的值为一1,当结点加 入到树中时，该结点pare nt的值为其双亲结点在数组 HuffNode中的序号，就不会是1 了。构造哈夫曼树时，首先将由n个字符形成的n个叶结点存放到数组 HufNode的前n个分量中，然后根据前面介绍的哈夫曼方法的基本思想，不断将两个小子树合并为一个较 大的子树，每次构成的新子树的根结点顺序放到HufNode数组中的前n个分量的后面。下面给出哈夫曼树的构造算法。const maxvalue
10、= 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: integer;beginreadln(n);
11、 输入叶子结点个数 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-1 do 构造哈夫曼树 beginm1:=MAXV ALUE; m2:=MAXV ALUE;x1:=0; x2:=0;for j:=0 to n+i-1 doif (HuffNodej.wei
12、ghtm1) and (HuffNodej.parent=-1) then begin m2:=m1; x2:=x1;m1:=HuffNodej.weight; x1:=j;endelse if (HuffNodej.weightm2) and (HuffNodej.parent=-1) then begin m2:=HuffNodej.weight; x2:=j; end; 将找出的两棵子树合并为一棵子树 HuffNodex1.parent:=n+i; HuffNodex2.parent:=n+i;HuffNoden+i.weight:= HuffNodex1.weight+HuffNode
13、x2.weight;HuffNoden+i.lchild:=x1; HuffNoden+i.rchild:=x2;end;end;7.3哈夫曼树在编码问题中的应用在数据通讯中，经常需要将传送的文字转换成由二进制字符0,1组成的二进制串，我们称之为编码。例如，假设要传送的电文为ABACCDA，电文中只含有A，B，C，D四种字符，若这四种字符采用表 7.3 (a)所示的编码，则电文的代码为长度为21。在传送电文时，我们总是希望传送时间尽可能短，这就要求电文代码尽可能短，显然，这种编码方案产生的电文代码不够短。表7.3 (b)所示为另一种编码方案，用此编码对上述电文进行编码所建立的代码为长度为14。
14、在这种编码方案中，四种字符的编码均为两位，是一种等长编码。如果在编码时考虑字符出现的频率，让出现频 率高的字符采用尽可能短的编码，出现频率低的字符采用稍长的编码，构造一种不等长编码，则电文的代码就可能更短。如当字符A，B，C，D采用表7.3 (c)所示的编码时，上述电文的代码为 长度仅为13。表b表c字符编码A000B010C100D111表a字符编码A00B01C10D11字符编码A0B110C10D111字符编码A01B010C001D10表d表7.3字符的四种不同的编码方案哈夫曼树可用于构造使电文的编码总长最短的编码方案。具体做法如下：设需要编码 的字符集合为d1 , d2,，dn,它们在电文中出现的次数或频率集合为 w1 , w2 ,， wn，以d1, d2,，dn作为叶结点，w1, w2,，wn作为它们的权值，构造一棵哈夫 曼树，规定哈夫曼树中的左分支代表 0,右分支代表1,则从根结点到每个叶结点所经过的 路径分支组成的0和1的序列便
