最优二叉树的逆推调位启发式算法设计

针对构造有个带权叶子结点的最优二叉树提出一种新颖的启发式算法,该算法根据递推算法的逆推原理,利用结点位置的调动产生的权的变化值来决定节点在最优二叉树中的位置。该算法在使二叉树达到最优的运算过程中,完全区别于以往的哈夫曼算法。逆推调位算法步骤简明,速度迅捷,最后以举例的方式说明该算法的实效性。

\\ \\\———————————————————————————————————————— —————————————————————————————————————————————————

研究与开发————————一———

—

—

—

最优二叉树的逆推调位启发式算法设计汪永强(州交通大学交通运输学院，州兰兰 7 00 ) 30 0

摘

要：针对构造有个带权叶子结点的最优二又树提出一种新颖的启发式算法 .算法根据递推算该法的逆推原理，利用结点位置的调动产生的权的变化值来决定节点在最优二叉树中的位

置。算法在使二叉树达到最优的运算过程中，全区别于以往的哈夫曼算法。推调位算该完逆法步骤简明，度迅捷，速最后以举例的方式说明该算法的实效性。关键词：调位：逆推；最优二叉树

0引

言

叉树的任何叶子结点在不同层间任一位置调动 .都会使变更后的二又树的带权路径长度咒增大 .即A WP>。就是说 .于一棵二叉树做“探”位变 LO也对试调更，如果变更后带权路径长度咒减小。 AWP< 即 L O.

最优二叉树，称哈夫曼 ( a m n树 .造最优又 H f a)构 f二叉树的方法 .被称作哈夫曼算法。前在构造带权又之路径长度最小的二叉树时，哈夫曼算法是唯一、 也是不得不被应用的新设计的逆推调位算法利用递

那么该调位是趋优的如果“探”试的任一调位变更都会使带权路径长度增大 .△咒> .么该调即 0那位是过优的 .该二叉树先前已经达到最优。即

推算法的逆推原理 .根据被处理结点位置移动产生的权的变化值确定各个结点的精确位置它不但可以较

快使目标达到最优 .而且能够在最优二叉树的编排同时方便记载结点的位置由于递推调位算法在运算过程中的比较次数少 .所以使得运算的整体速度比哈夫

曼算法更快

1逆推调位算法的思路 逆推调位算法是利用递推算法的逆推原理 .结合初始满二叉树的形态和各个叶子节

点权重的关系 .依据被处理结点位置“探”位产生的二叉树权变化值试调△咒来决定结点的相应位置 .从而使二叉树达到整图 1 图2

如图所示，图 1叉树变更为图 2二叉树 .将二即带权路径为 7的叶子结点上调，调位变更使=

=, 7

体优化具体来讲 .是当二叉树的某个结点位置变更时，就 带权路径长度咒发生变化叶子结点在二叉树中位置上调，权路径长度带带权路径长度减小；子结点位置下调，叶 相应地增大。

2 3 5, WP=—<,以该变更是趋优的。+= A L 57 0所

规定在开始阶段初步位于在权值较小的叶子结点前面，且所有的叶子结点均坐落在二叉树的底层。并使得在调位变更的过程中 .生的事件都是位置“探”发试

上调 .产生的结果均趋优 .即变更的带权路径长度AWP<。照相应的顺序判断到某个结点，位变更 LO按调产生的带权路径长度△咒> 0时 .断定最优即

最优二叉树要求其带权路径长度 WP L在一定权值条件下构成的所有二叉树中最小。而言之。优二换最收稿日期：0 0 0 2 2 1—1— 7修稿日期： 0 0 1 7 2 1 -1 -1

作者简介：汪永强 (95 )男，肃临泽人，读硕士研究生，究方向为铁路交通规划与管理 18 -,甘在研

现代计算机

2 1 .1 0 0 1