strtree.cpp

本代码演示了平衡排序二叉树的实现

#include "StrTree.h"
auto_arr<int> tree::tree_1(int num,std::istream&i){
	if(num<0)num=0;
	auto_arr<int> pint((num>2)?(new int[num-1]):(new int[1]));
	pint[0]=num;
	for(int c=1;c<=num-2;c++)i>>pint[c];
	return pint;
}
void tree::tree_2(int*tree,std::ostream&o){
	o<<tree[0]<<'\t';
	for(int i=1;i<=tree[0]-2;i++)o<<tree[i]<<'\t';
}
bool tree::tree_3(int*tree){
	int num=tree[0];
	if(num<0)return false;
	for(int i=1;i<=num-2;i++){
		if(tree[i]<0)return false;
		if(tree[i]>num)return false;
	}
	return true;
}
auto_arr<int> tree::tree_4(int*tree){
	auto_arr<int> edge;
	if(!tree::tree_3(tree)){
		edge.reset(new int[1]);
		edge[0]=-1;
		return edge;
	}
	int num=tree[0];
	int i,j,k,x;
	edge.reset((num>1)?(new int[2*num-1]):(new int[1]));
	edge[0]=num;
	if(num<=1){
		return edge;
	}else if(num==2){
		edge[1]=1;edge[2]=2;
		return edge;
	}else{
		auto_arr<int> flags(new int[num+1]);
		auto_arr<int> tempd(new int[num]);	
		for(i=0;i<=num-2;i++)tempd[i]=tree[i];
		i=tempd[num-2];
		if(i==num){
			edge[(num<<1)-3]=num-1;edge[(num<<1)-2]=num;
		}else{
			edge[(num<<1)-3]=i;edge[(num<<1)-2]=num;
		}
		for(i=1;i<=num-2;i++){
			for(x=0;x<=num;x++)flags[x]=1;
			for(x=1;x<=num-2;x++)flags[tempd[x]]=0;
			for(x=1;x<=num;x++)if(flags[x]==1)break;
			j=x;
			k=tempd[i];
			edge[(i<<1)-1]=j;edge[i<<1]=k;
			tempd[i]=j;
		}
		return edge;
	}
}
void tree::tree_5(int*edges,std::ostream&o){
	o<<edges[0]<<'\n';
	for(int i=1;i<=edges[0]-1;i++){
		o<<edges[(i<<1)-1]<<'\t'<<edges[i<<1]<<'\n';
	}
}
auto_arr<int> tree::tree_6(int*edges){
	auto_arr<int> str;
	int num=edges[0];
	int i,j,k,x;
	str.reset((num>2)?(new int[num-1]):(new int[1]));
	str[0]=num;
	if(num>=3){
		auto_arr<int> flags(new int[num+1]);
		auto_arr<int> tempe(new int[num<<1]);
		for(i=1;i<=num;i++)flags[i]=0;
		for(i=1;i<=(num-1)*2;i++){
			tempe[i]=edges[i];
			flags[edges[i]]++;
		}
		for(i=1;i<=num-2;i++){
			for(j=1;j<=num;j++)if(flags[j]==1)break;
			for(k=1;k<=num-1;k++){
				if(tempe[(k<<1)-1]==j){x=tempe[k<<1];break;}
				else if(tempe[k<<1]==j){x=tempe[(k<<1)-1];break;}
			}
			tempe[(k<<1)-1]=tempe[k<<1]=0;
			flags[j]--;
			flags[x]--;
			str[i]=x;
		}
	}
	return str;
}
auto_arr<int> tree::tree_7(int num,std::istream&i){
	if(num<0)num=0;
	auto_arr<int> pint((num>1)?(new int[2*num-1]):(new int[1]));
	pint[0]=num;
	for(int c=1;c<=num*2-2;c++)i>>pint[c];
	return pint;
}