《最优二叉树——哈夫曼树》由会员分享，可在线阅读，更多相关《最优二叉树——哈夫曼树（17页珍藏版）》请在金锄头文库上搜索。
1、最优二叉树哈夫曼树【引入】 在实际应用中，常常要考虑一个问题：如何设计一棵二叉树，使得执行路径最短，即 算法的效率最高。例 7.1 快递包裹的邮资问题 假设邮政局的包裹自动测试系统能够测出包裹的重量，如何设计一棵二叉树将包裹根 据重量及运距进行分类从而确定邮资。国内快递包裹资费 单位：元 （2004 年 1 月 1 日起执行）运距（公里）首重1000克5000克以内续重每500克5001克以上续重每500克=5005.002.001.005006.002.501.3010007.003.001.6015008.003.501.9020009.004.002.20250010.004.502.5
2、0300012.005.503.10400014.006.503.70500016.007.504.30600020.009.006.00表 7.1 国家邮政局制定的快递包裹参考标准根据表 7.1 可以制定出许多种二叉树，但不同的二叉树判定的次数可能不一样，执行 的效率也不同。例 7.2 铁球分类现有一批球磨机上的铁球，需要将它分成四类：直径不大于20 的属于第一类;直径大 于 20而不大于50的属于第二类；直径大于50而不大于100 的属于第三类；其余的属于第 四类；假定这批球中属于第一、二、三、四类铁球的个数之比例是1:2:3:4。我们可以把这个判断过程表示为图 7.1中的两种方法：图 7
3、.1 两种判断二叉树示意图 那么究竟将这个判断过程表示成哪一个判断框，才能使其执行时间最短呢？让我们对 上述判断框做一具体的分析。假设有 1000个铁球，则各类铁球的个数分别为：100、200、300、400；对于图 7.1中的左图和右图比较的次数分别如表7.2所示：左图序号比较式比较次数1a=2010002a=509003a=100700合计2600右图序号比较式比较次数1a10010002a506003a=20300合计1900表 7.2 两种判断二叉树比较次数过上述分析可知，图7.1 中右图所示的判断框的比较次数远远小于左图所示的判断框 的比较次数。为了找出比较次数最少的判断框，将涉及到
4、树的路径长度问题。7.1哈夫曼树的基本概念最优二叉树，也称哈夫曼(Haffman)树，是指对于一组带有确定权值的叶结点，构 造的具有最小带权路径长度的二叉树。那么什么是二叉树的带权路径长度呢？ 在前面我们介绍过路径和结点的路径长度的概念，而二叉树的路径长度则是指由根结 点到所有叶结点的路径长度之和。如果二叉树中的叶结点都具有一定的权值，则可将这一 概念加以推广。设二叉树具有n个带权值的叶结点，那么从根结点到各个叶结点的路径长 度与相应结点权值的乘积之和叫做二叉树的带权路径长度，记为：nWPL=Y W Lk=1 k k其中Wk为第k个叶结点的权值，Lk为第k个叶结点的路径长度。如图7.2所示的二
5、 叉树，它的带权路径长度值WPL=2X 2+4 X 2+5 X 2+3 X 2=28。在给定一组具有确定权值的叶结点，可以构造出不同的带权二叉树。例如，给出4个 叶结点，设其权值分别为1， 3， 5， 7，我们可以构造出形状不同的多个二叉树。这些形状不同的二叉树的带权路径长度将各不相同。图7.3给出了其中5个不同形状的二叉树。这五棵树的带权路径长度分别为：a) WPL=1X2+3X2+5X2+7X2=32b) WPL=1X3+3X3+5X2+7X1=29c) WPL=1X2+3X3+5X3+7X1=33d) WPL=7X3+5X3+3X2+1X1=43(a)e) WPL=7X1+5X2+3X3
6、+1X3=29图 7.3 具有相同叶子结点和不同带权路径长度的二叉树由此可见，由相同权值的一组叶子结点所构成的二叉树有不同的形态和不同的带权路 径长度，那么如何找到带权路径长度最小的二叉树(即哈夫曼树)呢？根据哈夫曼树的定 义，一棵二叉树要使其 WPL 值最小，必须使权值越大的叶结点越靠近根结点，而权值越 小的叶结点越远离根结点。哈夫曼(Haffman)依据这一特点于1952年提出了一种方法，这种方法的基本思想是：(1) 由给定的n个权值Wl, W2,，Wn构造n棵只有一个叶结点的二叉树，从 而得到一个二叉树的集合卩=口1, T2,，Tn；(2) 在 F 中选取根结点的权值最小和次小的两棵二叉
7、树作为左、右子树构造一棵新 的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和；(3) 在集合 F 中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集 合F中；(4) 重复(2) (3)两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的 哈夫曼树。由于这种算法是哈夫曼最早提出的，所以将最优二叉树称为哈夫曼树。图7.4给出了前面提到的叶结点权值集合为=1, 3, 5, 7的哈夫曼树的构造过程。可以计算出其带权路径长度为29，由此可见，对于同一组给定叶结点所构造的哈夫曼树，树的形状可能不同,但带权路径长度值是相同的,一定是最小的。7. 2 哈夫曼树的构造算法从上述算法
8、中可以看出，F实际上是森林，该算法的思想是不断地进行森郴中的二 叉树的“合并”,最终得到哈夫曼树。算法一：在构造哈夫曼树时，可以设置一个结构数组Hu ffNode保存哈夫曼树中各结点的信息, 根据二叉树的性质可知,具有 n 个叶子结点的哈夫曼树共有 2n1 个结点,所以数组 HuffNode的大小设置为2n1,数组元素的结构形式如下：weightlchildrchildparent其中，weight域保存结点的权值，lchild和rchild域分别保存该结点的左、右孩子结点 在数组 HuffNode 中的序号，从而建立起结点之间的关系。为了判定一个结点是否已加入 到要建立的哈夫曼树中，可通过p
9、arent域的值来确定。初始时parent的值为一1,当结点加 入到树中时,该结点parent的值为其双亲结点在数组HuffNode中的序号，就不会是一1 了。构造哈夫曼树时，首先将由n个字符形成的n个叶结点存放到数组HuffNode的前n 个分量中，然后根据前面介绍的哈夫曼方法的基本思想，不断将两个小子树合并为一个较 大的子树，每次构成的新子树的根结点顺序放至Hu ffNode数组中的前n个分量的后面。下面给出哈夫曼树的构造算法。const maxvalue= 10000;定义最大权值maxleat=30;定义哈夫曼树中叶子结点个数maxnode=maxleaf*2-1;type Hnode
10、Type=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);输入叶子结点个数for i:=0 to 2*n-l do数组 HuffNode初始化beginHuffNodei.weight=0;HuffNodei.
11、parent=-l;HuffNodei.clhild=- l ;HuffNodei.rchild=-l;end;for i:=0 to n-1 do read(HuffNodei.weight); 输入n个叶子结点的权值for i:=0 to n-l do构造哈夫曼树beginm1:=MAXVALUE; m2:=MAXVALUE;x1:=0; x2:=0;for j:=0 to n+i-1 doif (HuffNodej.weightm1) and (HuffNodej.parent=-1) then begin m2:=m1;x2:=x1;m1:=HuffNodej.weight; x1:=j;endelse if (HuffNodej.weight=2 DO BEGINInsert(a,i); 对a的前i个元素按Data域进行排序Ft.Data:二al.Data+a2.Data; 生成新的二叉树 Ft.lChild:=a1.Addr;Ft.rChild:=a2.Addr;a1.Data:=Ft.Data; 修改森林 a1.Addr:=t;a2.Data:=ai.Data; 修改森林 a2.Addr:=ai.Addr;i:=i-1; 二叉树数目减一t:=t+1;END;END;
