1．基本东西：

形象来说，外部节点表示选手捉对厮杀，内部节点表示比赛的胜者（败者）。定

义如下：对于n名选手，赢者树是一棵含n个外部节点，n-1个内部节点的完全二叉树

，其中每个内部节点记录了相应赛局的赢家（或输家）。

赢者树的一个优点在于即使一名选手得分改变了，也只需修改从它到根的那条路径

，而不必改变其他比赛结果。

2．抽象数据描述-WinnerTree

WinnerTree{

实例：

完全二叉树，每个节点表示相应比赛的赢者，外部节点表示选手；

操作：

Creat()---创建一个空的赢者树；

Initialize(a,n)：对有n个选手a[1:n]的赢者树进行初始化；

Winner()---返回比赛的赢者；

Replay(i)---选手i变化时，重组赢者树；

}；

3．类WinnerTree （202.38.64.10/~wurong/Ctree.rar）

n名选手的赢者树需要n-1个内部节点t[1:n-1]。选手（外部节点）用e[1:n]表示

。故t为数组e的一个索引而且类型为int。t给出了赢者树中节点i对应比赛的

赢者。为了实现ADT操作，必须能够确定外部节点e的父节点t[p]。根据赢者树完

全二叉树的特点，最低层最左端的内部节点编号为2S,这里s=log2(n-1)因此最低层

内部节点数目为n-2S，那么相应的最低层的外部节点数目LowExt应该为这个数值的

2倍，那么倒数第二层的最左端外部节点号为LowExt+1，设offset=2S+1-1，可知对

于任何外部节点e，其父节点t[p]满足一下关系：

p== (i+offset)/2 i<=LowExt

(i-LowExt+n-1)/2 i>LowExt

类定义：私有成员包括：MaxSize(允许最大选手数),n(赢者树初始化时选手数)

,t(内部节点数组),e(外部节点数组),LowExt和Offset。通过适当定义Winner，可以

构造最小赢者树，最大赢者树等。初始化和replay函数是通过比赛来进行的。

4．输者树

对于函数RePlay(i)函数，采用输者树效率比赢者树高，但是也仅限于这个情况

而已。

5．应用

①最先匹配法求解箱子装载问题：

问题描述：若干个容量为c的箱子和n个待装入箱子的物品，物品i需要占用s

个单元，所谓成功装载是把所有物品装入箱子而不溢出，而最优装载则是指使用了

最少箱子的成功装载。

对于此类箱子问题，流行4种算法：

A．最先匹配法（FF）：物品按照1,2,…,n的顺序装入箱子，假设箱子从左向右

排列，每一物品i放入可盛载它的最左箱子。

B．最优匹配法（BF）：设cAvail[j]为箱子j的可用容量，出示时所有都为c，物

品i放入具有最小cAvail且容量大于s的箱子中

C．最先匹配递减法（FFD）：与FF类似，区别在于各物品首先按照容量递减的次

序排列。

D．最优匹配递减法（BFD）：于BF类似，区别在于各物品首先按照容量递减的次序

排列。

这里设计最先匹配程序。程序首先要求输入物品数量n及每个箱子的容量c。假定容

量及空间需求均为整数，接下来程序要求输入n个物品并限制每个物品孔间<=c。最

后再调用函数FirstFitBack，将物品分派到各个箱子。对于使用FFD策略的程序，只

需将源程序稍作修改，即在调用FirstFitBack前按递减顺序对物品进行排序。

对于FirstFitBack函数，选手i代表箱子i当前的容量，所有箱子容量初始化为c。该

函数假定，当比赛开始时左边选手是赢者，除非右边选手比较大。

具体代码见firstfit.cpp

②用相邻匹配法求解箱子装载问题：

Next Fit策略中，开始将物品1放入箱子1，对于其余物品，则从最后使用的箱子的

下一个箱子开始。比如箱子1~b正在使用，则可认为这些箱子排列成环状：i!=b时，

i的下一个箱子为i+1；i=b时，i的下一个箱子为箱子1。若上一个物品放入了箱子j

，则从箱子j的下一个箱子开始不断查找后续箱子，直到找到具有足够空间的箱子或

者又回到箱子j。若没有找到合适的，则启用一新箱子。