winnertree.h

来自「清华大学计算机系数据结构课程教材《数据结构 用面向对象方法和C++描述》（殷人昆」· C头文件 代码 · 共 33 行

#ifndef WINNER_TREE
#define WINNER_TREE
#define maxValue 10000
template <class T>
class WinnerTree {
private:
	int maxSize;		//允许的最大选手数
	int n;			//当前大小(外部结点数)
	int lowExt;		//最远层外部结点数
	int offset;			//偏移(加1即为第1个外结点)
	int *t;			//胜者树数组
	T *e;			//选手数组
	void Play (int k, int lc, int rc);
public:
    //static const T maxValue = 10000;	//序列中不可能的大值
    WinnerTree (int TreeSize = 20)	//构造函数
         : maxSize(TreeSize), n(0) { 
	t = new int[TreeSize];
	for(int i = 0; i < TreeSize; ++i)
	t[i] = maxValue;
	}		
    ~WinnerTree() { delete []t; }	//析构函数
    bool Initial (T a[], int size);
    bool rePlay (int i);
							//重构
    void Update() { e[t[1]] = maxValue; }	//修改
    int Winner() const { return (n != 0) ? e[t[1]] : 0; }	//取最终胜者
	int Winner (int i) const { return (i < n) ? t[i] : 0; }//取第i个胜者
	int Winner (int a, int b) { return (e[a] <= e[b]) ? 
                       a : b;}	//取两外结点胜者
};
#endif