为实习准备的数据结构（6）-- 优胜树与淘汰树

#include<iostream>
#include<vector>

using namespace std;

class Tree_Node {
private:
	success_tree* father;	//每个节点都会有父节点
	int val;	//当前节点的值

public:
	Tree_Node(int val) :val(val) {}
};

vector<int> return_temp(vector<int>& temp) {
	vector<int> t;
	for (int i = 0, j = 1; j< temp.size(); i += 2, j += 2) {
		t.push_back(max(temp[i], temp[j]));
	}
	return t;
}

class success_tree {

public:
	vector<vector<int>> res;
	vector<vector<int>> target;

	success_tree(vector<vector<int>>& target) {
		this->target = target;
	}

	vector<vector<int>> create_tree() {
		/*
			参数：待排序的归并序列
	
			操作方法：
			1、遍历当前归并序列，取出每个序列的尾部数据，设置序列数为2的n次方
			2、获得第一批父节点，存入一组数组中
			3、再获取一批父节点，存入下一组数组中
			4、重复步骤三，直到某组数组中只有一个数据
	
			返回值：
			该二维数组
		*/
		
		int sz = target.size();

		vector<int> temp;
		for (int i = 0; i < sz;i++) {
			temp.push_back(target[i].back());
		}
		temp = return_temp(temp);

		do{
			temp = return_temp(temp);
			res.push_back(temp);
		} while (temp.size() > 1);
	}

	void run() {
		/*
		函数功能：完成排序
		操作手法：
		1、取出根节点之后，跟尾结点进行比对，看是哪一个分支分出的
		2、尾结点向前递进，采用减一除二的推导式
		3、如果有某个分支为空，则设置该位置为INT_MAX，让它们永远没有机会再出现
		4、记录一个标志位，标记全部为空的时候退出循环
		*/

		int flag = target.size();	//4
		
		while (flag) {
			int out = target.back()[0];
			cout << out << endl;	//这里就不弄其他的了，直接输出吧
			for (int i = 0; i < res.size(); i++) {
				for (int j = 0; j < res[i].size(); j++) {
					if (out == res[i][j]) {	//1

						if (i == 0) {
							target[i].pop_back();

							if (target[i].empty()) {	//3
								target[i].push_back(INT_MAX);
								flag--;
							}

							res[i][j] = target[i].back();
						}
						else {
							res[i][j] = max(res[i-1][2*j], res[i - 1][2 * j + 1]);
						}
					}
				}
				
			}
		}
	}
};

  a：b3 Vs b4，b3胜b4负，内部结点ls[4]的值为4，表示b4为败者；胜者b3继续参与竞争。
  b：b3 Vsb0，b3胜b0负，内部结点ls[2]的值为0，表示b0为败者；胜者b3继续参与竞争。
  c：b1 Vs b2，b1胜b2负，内部结点ls[3]的值为2，表示b2为败者；胜者b1继续参与竞争。
  d：b3 Vs b1，b3胜b1负，内部结点ls[1]的值为1，表示b1为败者；胜者b3为最终冠军，用ls[0]=3，记录的最后的胜者索引。

void Adjust(int s)
{
	int t=(s+k)/2;   //t为内部结点，也就是s的父节点
    
    while(t>0){
    	if(b[s]>b[ls[t]]){
	        int tmp=s;
            s=ls[t];     //s记录新的胜者
            ls[t]=tmp;
	    }
	    t=t/2;
	}
    ls[0]=s;
}
 
void  CreateLoserTree()
{
	int i;
    b[k]=MIN;
    
    for(i=0;i<k;i++)
    	ls[i]=k;

    for(i=k-1;i>=0;i--)
    	Adjust(i);
}