SCAU------8608二叉並べ替えツリーを実現する各種アルゴリズム(2)

Descriptionは関数を用いて,(1)新しいノードを挿入する(2)前順,中順,後順二叉木を巡る(3)中順に巡る非再帰アルゴリズム(4)階層二叉木を巡る(5)二叉木の中で所与のキーワード(関数戻り値が成功1,失敗0)(6)各ノードを交換する左右のサブツリー(7)二叉木の深さ(8)葉のノード数を求める
入力フォーマット1行目:ツリーを作成するためのノード数n 2行目:n個の整数を入力し、3行目をスペースで区切る:検索対象キーワード4行目を入力:検索対象キーワード5行目を入力:挿入対象キーワードを入力
出力フォーマット1行目:ツリーの先頭の巡回シーケンス2行目:ツリーの中の巡回シーケンス3行目:ツリーの後の巡回シーケンス4行目:検索結果5行目:検索結果6行目~8行目:新しいノードを挿入したツリーの先頭、中央、シーケンス遍歴シーケンス9行目:新しいノードを挿入したツリーの中シーケンス遍歴シーケンス(非再帰アルゴリズム)10行目:新しいノードを挿入したツリーの階層遍歴シーケンス11行目~13行目:各ノードの左右のサブツリーを1回目に交換した後の先、中、後シーケンス遍歴シーケンス14行目~16行目:各ノードの左右のサブツリーを2回目に交換した後の先、中、後順遍歴シーケンス17行目:二叉木の深さ18行目:葉結点数
入力サンプル7 40 20 60 18 50 56 90 18 35 30
出力サンプル40 20 20 18 60 50 56 90 18 20 40 50 50 56 60 90 18 50 50 50 50 50 90 60 1 0 40 20 18 30 60 50 56 90 50 50 50 50 50 50 18 30 30 30 30 20 20 50 60 40 18 20 30 30 30 40 40 40 40 50 50 50 50 50 60 60 60 60 50 50 50 50 50 50 50 50 60 60 60 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 40 20 20 20 20 20 20 20 20 30 30 30 30 30 30 30 50 50 50 50 50 60 90 90 18 30 20 50 50 50 40 40 4
注意事項と構想はコードの中で
コードは次のとおりです.

#include 
#include 
#include 
#include 
using namespace std;
typedef struct BSTNode
{
     
	int data;
	struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;

void Pre(BSTree T)//     
{
     
	if(T) 
	{
     
		cout<<T->data<<" ";
		Pre(T->lchild);
		Pre(T->rchild); 
	}
}

void In(BSTree T)//     
{
     
	if(T) 
	{
     
		In(T->lchild);
		cout<<T->data<<" ";
		In(T->rchild); 
	}	
} 

void Post(BSTree T)//     
{
     
	if(T) 
	{
     
		Post(T->lchild);
		Post(T->rchild);
		cout<<T->data<<" "; 
	}	
} 

void Insert(BSTree &T,int e)//           
{
     
	if(!T)//      ，     
	{
     
		BSTree S;
		S=new BSTNode;  //      
		S->data=e;
		S->lchild=S->rchild=NULL;
		T=S;//    *S            
	}
	else if(e<T->data) Insert(T->lchild,e);
	else if(e>T->data) Insert(T->rchild,e); 
}

void CreateBSTree(BSTree &T,int n)//        
{
     
	T=NULL;
	int e;
	for(int i=0;i<n;i++)
	{
     
		cin>>e;
		Insert(T,e);
	}
} 

//         ，      ，        ，               
//          ，                   ，
//               
void Inf(BSTree T)//           
{
      //     p
//        ，  p    p         p，      p       
//       ，           ，       ，      p          
//  p            
	stack  < BSTree > s;
	BSTree p;
	p=T;
	while(p||!s.empty())
	{
     
		while(p)
		{
     
			s.push(p);//      
			p=p->lchild;//      
		}
		if(!s.empty()) //        
		{
     
			p=s.top();
			cout<<p->data<<" ";//      
			s.pop();//   
			p=p->rchild;//      
		}
	}
}

void Floor(BSTree T)//     
{
     
	queue <BSTree> q;
	if(T) q.push(T);//       
	while(!q.empty())//     
	{
     
		cout<<q.front()->data<<" ";
		if(q.front()->lchild) 
		q.push(q.front()->lchild);//        ，      
		if(q.front()->rchild) 
		q.push(q.front()->rchild);//        ，      
		q.pop();//           
	} 
} 

BSTree Search(BSTree T,int e)//         
{
     
	if(!T||T->data==e) return T;
	else if(e< T->data) return Search(T->lchild,e);
	else if(e> T->data) return Search(T->rchild,e); 
} 

int Depth(BSTree T)//       
{
     
	if(T==NULL) return 0;
	else
	{
     
		int m=Depth(T->lchild);
		int n=Depth(T->rchild);
		return m>n?m+1:n+1;
	}
} 

int Count(BSTree T)//     
{
     
	if(!T) return 0;//        
	else
	{
     
		if(T->lchild||T->rchild) 
		return Count(T->lchild)+Count(T->rchild);
		if(T->lchild==NULL&&T->rchild==NULL) return 1;	
	}
}

BSTree Change(BSTree &T)//          
{
     
	if(T)
	{
     
		if(T->lchild||T->rchild)
		{
     
			BSTree p,q;
			p=Change(T->lchild);
			q=Change(T->rchild);
			T->lchild=q;
			T->rchild=p;
		}
	}
	return T;
}

int main()
{
     
	//freopen("data.txt","r",stdin);
	int n;
	cin>>n;
	BSTree T;
	int x,y,z;
	CreateBSTree(T,n);
	Pre(T);cout<<endl;
	In(T);cout<<endl;
	Post(T);cout<<endl;
	cin>>x>>y>>z;
	if(Search(T,x)) cout<<"1"<<endl;
	else cout<<"0"<<endl; 
	if(Search(T,y)) cout<<"1"<<endl;
	else cout<<"0"<<endl; 
	Insert(T,z);
	Pre(T);cout<<endl;
	In(T);cout<<endl;
	Post(T);cout<<endl;
	Inf(T);cout<<endl;
	Floor(T);cout<<endl;
	Change(T);
	Pre(T);cout<<endl;
	In(T);cout<<endl;
	Post(T);cout<<endl;
	Change(T);
	Pre(T);cout<<endl;
	In(T);cout<<endl;
	Post(T);cout<<endl;
	cout<<Depth(T)<<endl;
	cout<<Count(T)<<endl;
	return 0;	
}

/*
  ： 
5
7 4 9 5 8
5
6
2

  ：
7 4 5 9 8
4 5 7 8 9
5 4 8 9 7
1
0
7 4 2 5 9 8
2 4 5 7 8 9
2 5 4 8 9 7
2 4 5 7 8 9
7 4 9 2 5 8
7 9 8 4 5 2
9 8 7 5 4 2
8 9 5 2 4 7
7 4 2 5 9 8
2 4 5 7 8 9
2 5 4 8 9 7
3
3
*/