twotree.cpp

二叉树的基本操作

#include<iostream.h>

struct BiTree
{	
	int data;
	BiTree*Lchild,*Rchild;	
	BiTree()
	{
		data=0;
		Lchild=0;
		Rchild=0;
	}
	~BiTree()
	{
		delete Lchild;
		delete Rchild;
	}
	
};
typedef BiTree*BTree;

void Insert(BTree&T,int Data);//向二叉树中插入结点
void Creat(BTree&T);//建立排序二叉树
int Find(BTree&T,BTree&f,BTree&p,int Data);//查找结点
int  Delete(BTree&T,int Data);//删除结点
void Delete_One(BTree&p);
void DLR_OutPut(BTree&T);//先根序遍历二叉树
void LDR_OutPut(BTree&T);//中根序遍历二叉树
void LRD_OutPut(BTree&T);//后根序遍历二叉树

void Insert(BTree&T,int Data)
{
	BTree s;	
	s=new BiTree;
	s->data=Data;	
	s->Lchild=0;
	s->Rchild=0;
	if(T==0)T=s;	
	else if(s->data<T->data)Insert(T->Lchild,Data);
	else if(s->data>T->data)Insert(T->Rchild,Data);	
}

void Creat(BTree &T)	
{	
	if(T)T=0;//T=0便于重新建二叉树
	int x;		
	cin>>x;
	while(x!=-1)
	{		
		Insert(T,x);
		cin>>x;
	}
}

int Find(BTree &T,BTree&f,BTree &p,int Data)
{

	if(T==0)
	{		
		//cout<<"树空！"<<endl;		
		p=f;
		return 0;
	}
	else 
		if(Data==T->data)	
		{		
			p=T;
			return 1;
		//	cout<<"查找成功！"<<endl;			
		}	
		else 
			if(Data<T->data)
				Find(T->Lchild,T,p,Data);	
			else 
				if(Data>T->data)Find(T->Rchild,T,p,Data);	
}

int Delete(BTree &T,int data)
{
	if(T==0)return 0;
	else
	{
		if(T->data==data)
		{
			Delete_One(T);
			return 1;
		}
		else if(data<T->data)Delete(T->Lchild,data);	
		else if(data>T->data)Delete(T->Rchild,data);
	}
}

void Delete_One(BTree &p)//画图分析呀！！！！！！！！！！！！！！！
{
	BTree p1, p2;
	if(p->Rchild==0)
	{
		p1=p;
		p=p->Lchild;
		delete p1;
	}
	else if(p->Lchild==0)
	{
		p1=p;
		p=p->Rchild;
		delete p1;
	}
	else
	{
		p1=p;
		p2=p->Lchild;
		while(p2->Rchild)
		{
			p1=p2;
			p2=p2->Rchild;
		}
		p->data=p2->data;
		if(p1!=p)p1->Rchild=p2->Lchild;
		else p1->Lchild=p2->Lchild;
		delete p2;
	}
}

void DLR_OutPut(BTree &T)
{
	if(T==0);//cout<<"树空!";
	else 
	{	
		cout<<T->data<<'\t';
		DLR_OutPut(T->Lchild);			
		DLR_OutPut(T->Rchild);
	}
}

void LDR_OutPut(BTree &T)
{
	if(T==0);//cout<<"树空!";
	else 
	{	
		LDR_OutPut(T->Lchild);
		cout<<T->data<<'\t';	
		LDR_OutPut(T->Rchild);
	}
}

void LRD_OutPut(BTree &T)
{
	if(T==0);//cout<<"树空!";
	else 
	{	
		LRD_OutPut(T->Lchild);
		LRD_OutPut(T->Rchild);		
		cout<<T->data<<'\t';		
	}
}

void main()
{
	BTree T;
Labl_6:
	{	
		cout<<"请输入二叉树的结点值，以-1结束!"<<endl;	
		Creat(T);
	}	
Labl:
	{
		int m;
		cout<<endl;
		cout<<"排序二叉树已经建好，请选择操作："<<endl;
		cout<<"***************************************************************"<<endl<<endl;
		cout<<"          1: 先序遍历二叉树  2:中序遍历二叉树"<<endl;
		cout<<"          3: 后序遍历二叉树  4:向二叉树插入数值"<<endl;
		cout<<"          5: 查找一个结点    6:重新建立二叉树 "<<endl;
		cout<<"          7: 删除一个结点    8:退出程序"<<endl;
		cout<<"***************************************************************"<<endl<<endl;
		cin>>m;
		switch(m)
		{
		case 1 : goto Labl_1;break;		
		case 2 : goto Labl_2;break;		
		case 3 : goto Labl_3;break;
		case 4 : goto Labl_4;break;
		case 5 : goto Labl_5;break;
		case 6 : goto Labl_6;break;
		case 7 : goto Labl_7;break;
		case 8 : goto Labl_8;break;
		default: goto Labl;
		}	
	}
Labl_1:
	{	cout<<"先序遍历结果为:"<<endl;	   
		DLR_OutPut(T);
		cout<<endl;
		goto Labl;
	}
Labl_2:
	{
		cout<<"中序遍历结果为:"<<endl;
		LDR_OutPut(T);
		cout<<endl;
		goto Labl;
	}
Labl_3:
	{
		cout<<"后序遍历结果为:"<<endl;
		LRD_OutPut(T);
		cout<<endl;
		goto Labl;
	}
Labl_4:
	   {
		   cout<<"请输入要插入的值:"<<endl;
		   int v;
		   cin>>v;
		   Insert(T,v);
Labl_4_1:{	   
			 cout<<"继续插入 Y/N?"<<endl;		   
			 char flag;		   
			 cin>>flag;		   
			 switch(flag)		   
			 {		   
			 case 'Y':		   
			 case 'y':goto Labl_4;break;		   
			 case 'N':		   
			 case 'n':goto Labl;break;	   
			 default :goto Labl_4_1;		   
			 }
		 }//Labl_4_1
	   }//Labl_4
Labl_5:
	   { 
		   cout<<"请输入要查找的值:"<<endl;
		   BTree f=0,p=0;
		   int v;
		   cin>>v;
		   if(Find(T,f,p,v))cout<<"查找成功,其地址是:"<<p<<endl;
		   else cout<<"查找失败!"<<endl;
Labl_5_1:
		   { 
			 cout<<"继续查找 Y/N?"<<endl;		   
			 char flag;		   
			 cin>>flag;		   
			 switch(flag)		 
			 {		   
			 case 'Y':		   
			 case 'y':goto Labl_5;break;		   
			 case 'N':		   
			 case 'n':goto Labl;break;		   
			 default :goto Labl_5_1;		   
			 }		 
		   }//Labl_5_1
	   }//Labl_5
Labl_7:
	   {
		   cout<<"请输入要删除的值:"<<endl;
		   int v;
		   cin>>v;		   
		   if(Delete(T,v))cout<<"删除成功!"<<endl;
		   else cout<<"删除失败!"<<endl;
Labl_7_1:{
			 cout<<"继续删除 Y/N?"<<endl;		   
			 char flag;		   
			 cin>>flag;		   
			 switch(flag)		   
			 {			   
			 case 'Y':		   
			 case 'y':goto Labl_7;break;		   
			 case 'N':		   
			 case 'n':goto Labl;break;		   
			 default :goto Labl_7_1;
			 }
		 }//Labl_7_1
	   }//Labl_7
Labl_8:;
}