最优二叉树哈夫曼树..doc

最优二叉树——哈夫曼树 【 在实际应用中，常常要考虑一个问题：如何设计一棵二叉树，使得执行路径最短，即算法的效率最高。 例7.1快递包裹的邮资问题 假设邮政局的包裹自动测试系统能够测出包裹的重量，如何设计一棵二叉树将包裹根据重量及运距进行分类从而确定邮资。 国内快递包裹资费 单位：元 （2004年1月1日起执行） 运距首重1000克5000克以内续重每500克5001克以上续重500克=500 5.00 2.00 1.00 =1000 500 6.00 2.50 1.30 =1500 1000 7.00 3.00 1.60 =2000 1500 8.00 3.50 1.90 =2500 2000 9.00 4.00 2.20 =3000 2500 10.00 4.50 2.50 =4000 3000 12.00 5.50 3.10 =5000 4000 14.00 6.50 3.70 =6000 5000 16.00 7.50 4.30 6000 20.00 9.00 6.00 表7.1 国家邮政局制定的快递包裹参考标准 根据表7.1可以制定出许多种二叉树，但不同的二叉树判定的次数可能不一样，执行的效率也不同。 例7.2 铁球分类 现有一批球磨机上的铁球，需要将它分成四类：直径不大于20的属于第一类;直径大于20而不大于50的属于第二类；直径大于50而不大于100的属于第三类；其余的属于第四类；假定这批球中属于第一、二、三、四类铁球的个数之比例是1:2:3:4。 我们可以把这个判断过程表示为 图7.1中的两种方法： 图7.1 两种判断二叉树示意图 那么究竟将这个判断过程表示成哪一个判断框，才能使其执行时间最短呢？让我们对上述判断框做一具体的分析。 假设有1000个铁球，则各类铁球的个数分别为：100、200、300、400； 对于图7.1中的左图和右图比较的次数分别如表7.2所示： 左图 右图 序号 比较式 比较次数 序号 比较式 比较次数 1 a=20 1000 1 a100 1000 2 a=50 900 2 a50 600 3 a=100 700 3 a=20 300 合计 2600 合计 1900 表7.2 两种判断二叉树比较次数 过上述分析可知，图7.1中右图所示的判断框的比较次数远远小于左图所示的判断框的比较次数。为了找出比较次数最少的判断框，将涉及到树的路径长度问题。 7.1哈夫曼树的基本概念 最优二叉树，也称哈夫曼（Haffman）树，是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树。 那么什么是二叉树的带权路径长度呢？ 在前面我们介绍过路径和结点的路径长度的概念，而二叉树的路径长度则是指由根结点到所有叶结点的路径长度之和。如果二叉树中的叶结点都具有一定的权值，则可将这一概念加以推广。设二叉树具有n个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度，记为： WPL＝ Wk·Lk 其中Wk为第k个叶结点的权值，Lk 为第k个叶结点的路径长度。如图7.2所示的二叉树，它的带权路径长度值WPL＝2×2＋4×2＋5×2＋3×2＝28。 在给定一组具有确定权值的叶结点，可以构造出不同的带权二叉树。例如，给出4个叶结点，设其权值分别为1，3，5，7，我们可以构造出形状不同的多个二叉树。这些形状不同的二叉树的带权路径长度将各不相同。图7.3给出了其中5个不同形状的二叉树。 这五棵树的带权路径长度分别为： （a）WPL＝1×2＋3×2＋5×2＋7×2＝32 （b）WPL＝1×3＋3×3＋5×2＋7×1＝29 （c）WPL＝1×2＋3×3＋5×3＋7×1＝33 （d）WPL＝7×3＋5×3＋3×2＋1×1＝43 图7.2 一个带权二叉树 （e）WPL＝7×1＋5×2＋3×3＋1×3＝29 (a) (b) (c) (d) (e) 图7.3 具有相同叶子结点和不同带权路径长度的二叉树 由此可见，由相同权值的一组叶子结点所构成的二叉树有不同的形态和不同的带权路径长度，那么如何找到带权路径长度最小的二叉树（即哈夫曼树）呢？根据哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶结点越靠近根