最优二叉树哈夫曼树VIP专享

1 最优二叉树——哈夫曼树 【重点与难点】 1． 带权二叉树与哈夫曼树基本概念； 2． 构造哈夫曼树； 3． 哈夫曼编码及其算法实现。 【引入】 在实际应用中，常常要考虑一个问题：如何设计一棵二叉树，使得执行路径最短，即算法的效率最高。 例 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中的两种方法： 2 图 7.1 两种判断二叉树示意图 那么究竟将这个判断过程表示成哪一个判断框，才能使其执行时间最短呢？让我们对上述判断框做一具体的分析。 假设有 1000个铁球，则各类铁球的个数分别为：100、200、300、400； 对于图 7.1中的左图和右图比较的次数分别如表 7.2所示： 左图 右图 序号 比较式 比较次数 序号 比较式 比较次数 1 a<=20 1000 1 a>100 1000 2 a<=50 900 2 a>50 600 3 a<=100 700 3 a<=20 300 合计 2600 合计 1900 表 7.2 两种判断二叉树比较次数 过上述分析可知，图 7.1 中右图所示的判断框的比较次数远远小于左图所示的判断框的比较次数。为了找出比较次数最少的判断框，将涉及到树的路径长度问题。 7 .1 哈夫曼树的基本概念 最优二叉树，也称哈夫曼（Haffman）树，是指对于一组带有确定权值的叶结点，构造的具有最...