二叉树.cpp

实现构造一个二叉树、二叉树的遍历（递归与非递归方法）

#include<iostream>
using namespace std;
#define MAX_TREE_SIZE  100
#define TRUE 1
#define FALSE 0
#define  overflow -2
#define error 0
#define ok   1
typedef char status;
typedef   char TElemType;
typedef TElemType SqBiTree[MAX_TREE_SIZE];
SqBiTree bt;
typedef struct BiTNode{
TElemType   data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

  status InitBiTree(BiTree &T)
{  //初始化二叉树
   T=(BiTNode*)malloc(sizeof(BiTNode));
   if(!T)  exit(overflow);
   T=NULL;
   return ok;
}
  status DestroyBiTree(BiTree &T)
{  //销毁二叉树
  if(T)
  {  DestroyBiTree(T->lchild);
     DestroyBiTree(T->rchild);
	 free(T);
  }
  return ok;
} 
 
status  CreateBiTree(BiTree &T)
{  //创建一个二叉树 
	char ch;
	cin>>ch;
   if(ch=='#') T=NULL;
   else
   { if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))
      exit(overflow);
      T->data=ch;
      CreateBiTree(T->lchild);
	  CreateBiTree(T->rchild);
   }
   return ok;
}
status ClearBiTree(BiTree &T)
{  //清空二叉树  
	DestroyBiTree(T);
	T=NULL;
   return ok;
}
int BiTreeEmpty(BiTree T)
{  //二叉树为空返回TRUE，否则返回FALSE
	if(T==NULL)   
   return TRUE;
  else
	  return FALSE;
}
int BiTreeDepth(BiTree T)
{ //返回二叉树的深度
	int i,j;
   if(T==NULL)
	   return 0;
   else
   { i=BiTreeDepth(T->lchild);
     j=BiTreeDepth(T->rchild);
	 if(i>j)
		 return i+1;
	 else
		 return j+1;
   }
}
status Root(BiTree T)
{  //返回二叉树的根
	if(T)
    return T->data; 
   else
	   return error;
}

status printElement(TElemType e)
{  cout<<e;
   return ok;
}
status PreOrderTraverse(BiTree T,status(*visit)(TElemType e))
{//先序遍历二叉树
	
     if(T)
	 {  if(visit(T->data))
	      if(PreOrderTraverse(T->lchild,visit))
			  if(PreOrderTraverse(T->rchild,visit))
				  return ok;
		 return error;
	 }
	 else 
		 return  ok;
}
status search(BiTree T,TElemType e,BiTree p)
{  
	if(!T)
	{  p=NULL;
	  return error;
	}
     else if(T->data==e)
	 {p=T;
	  return ok;
	 }
	 else
	 {search(T->rchild,e,p);
	  search(T->lchild,e,p);
	   return ok;
	 }
}
status Value(BiTree T,TElemType e)
{   
	if(T==NULL)
    return error;
    if(T->data==e)
		return e;
	else  
	{  Value(T->lchild,e);
	   Value(T->rchild,e);
	}
	return ok;
}
status   Assign(BiTree T,TElemType &e,TElemType value)
{    if(T==NULL)
    return error;
    if(T->data==e)
	  e=value;
	else
	{	Assign(T->lchild,e,value);
	    Assign(T->rchild,e,value);
	}
	return ok;
} 
status Parent(BiTree T,TElemType e)
{   //若e是T的非根结点，则返回它的双亲，否则返回‘空’
     if(T==NULL||T->data==e)
		 return NULL;
	 if(T->lchild&&T->lchild->data==e)
	 {cout<< T->data<<endl;return ok;}
	  if(T->rchild&&T->rchild->data==e)
	  {  cout<< T->data<<endl;return ok;}
	
	 
       Parent(T->lchild,e);
	   Parent(T->rchild,e);
	   
	   return error;
	 
	   
	 
	 
}

status  LeftChild(BiTree T,TElemType e)
{  //返回e的左孩子。若e无左孩子，否则返回“空”
	 if(T==NULL)
		 
	 return NULL;
		 if(T->data==e)
		 {   if(T->lchild!=NULL)
		   cout<< T->lchild->data<<endl;

             else if(T->lchild==NULL)
		     
			 {cout<<"此结点无左孩子！"<<endl;return NULL;}
		 }
	     
		     LeftChild(T->lchild,e);
			 LeftChild(T->rchild,e);
	       return error;
		 

	
}
status RightChild(BiTree T,TElemType e)
{   //返回e的右孩子。若e无右孩子，否则返回“空”
     if(T==NULL)
	 return NULL;
		 if(T->data==e)
	   {   if(T->rchild!=NULL)
           cout<< T->rchild->data<<endl;
           else if(T->rchild==NULL)
		   {cout<<"此结点无右孩子！"<<endl;return NULL;}
	   }
	     
		RightChild(T->lchild,e);
		RightChild(T->rchild,e);
	    return error;
	   


}
status LeftSibling(BiTree T,TElemType e)
{   //返回e的左兄弟。若e无左兄弟或e是T的左孩子，否则返回“空”
	if(T==NULL)
		return NULL;
    else
	{
		 if(T->data==e||T->lchild==NULL||T->lchild->data==e)
		{cout<<"此结点无左兄弟！"<<endl;return NULL;}
         else if(T->rchild->data==e)
		cout<< T->lchild->data<<endl;
		 
         LeftSibling(T->lchild,e) ;
	     LeftSibling(T->rchild,e);
         return error;
	}
    
  

}
status RightSibling(BiTree T,TElemType e)
{   //返回e的右兄弟。若e无右兄弟或e是T的右孩子，否则返回“空”
   if(T==NULL) 
   return NULL;
   else 
   {if(T->data==e||T->rchild==NULL||T->rchild->data==e)
	 
   {cout<<"此结点无右兄弟！"<<endl; return NULL;}

   else  if(T->lchild->data==e)
		cout<< T->rchild->data<<endl;
   
	   RightSibling(T->lchild,e);
	   RightSibling(T->rchild,e);
	  
      return error;
   
   }
   
}
status InsertChild(BiTree T,TElemType e,int LR,BiTree c )
{    
     
     
     if(T!=NULL)
	 {if(T->data==e)
	      if(LR=0)
		  {  c->rchild=T->lchild;
		     T->lchild=c;
		       
			  return ok;
		  }
		  else if(LR=1)
		  {   c->lchild=T->rchild; T->rchild=c;
		      
			  return ok;
		  }
		  InsertChild(T->lchild,e,LR,c);
		  InsertChild(T->rchild,e,LR,c);
	 }
    else
       return ok;
}
status DeleteChild(BiTree T,TElemType e,int LR)
{    
     
	 if(T==NULL)
		  return ok;
     if(T->data==e)
	 {  
	     if(LR=0)
			 T->lchild=NULL;
		 if(LR=1)
			 T->rchild=NULL;
		return ok;
	 }
	   DeleteChild(T->lchild,e,LR);
	    DeleteChild(T->rchild,e,LR);

	return ok;
      
   
}
	

status InOrderTraverse(BiTree T,status(*visit)(TElemType e))
{ //中序遍历二叉树
   if(T)
   {if(InOrderTraverse(T->lchild,visit))
     if(visit(T->data))
		 if(InOrderTraverse(T->rchild ,visit))
			 return ok;
       return error;
   }
   else return ok;
}
status PostOrderTraverse(BiTree T,status(*visit)(TElemType e))
{//后序遍历二叉树
	if(T)
	{ if(PostOrderTraverse(T->lchild,visit))
	    if(PostOrderTraverse(T->rchild,visit))
			if(visit(T->data))
				return ok;
			return error;
	}
	else
		return ok;
}
void main()
{    BiTree T,c;TElemType e;int LR;
    InitBiTree(T);
    cout<<"输入为'#'时为空!\n"<<endl;
	cout<<"请输入你要建的二叉树："<<endl;
	CreateBiTree(T);
	cout<<"二叉树是否为空？若为空返回1，否则返回0。"<<endl;
	cout<<BiTreeEmpty(T)<<endl;
	cout<<"此二叉树的深度：";
	cout<<BiTreeDepth(T)<<endl;
	cout<<"此二叉树的根：";
    cout<<Root(T)<<endl;
    cout<<"先序遍历二叉数："<<endl;
	PreOrderTraverse(T,printElement);
	cout<<"\n";
	cout<<"中序遍历二叉数："<<endl;
	InOrderTraverse(T,printElement);
	cout<<"\n";
    cout<<"后序遍历二叉数："<<endl;
	PostOrderTraverse(T,printElement);
	cout<<"\n";
	
    
    cout<<"返回结点e的双亲:"<<endl;
    cout<<"e=";
	cin>>e;
    Parent(T,e); 
	
	cout<<"返回结点e的左孩子:"<<endl;
	cout<<"e=";
	cin>>e;
	LeftChild(T,e);
    cout<<"返回结点e的右孩子:"<<endl;
    cout<<"e=";
	cin>>e;
	RightChild(T,e);
    cout<<"返回结点e的左兄弟:"<<endl;
    cout<<"e=";
	cin>>e;
    cout<<LeftSibling(T,e)<<endl;
    cout<<"返回结点e的右兄弟:"<<endl;
    cout<<"e=";
	cin>>e;
	RightSibling(T,e);
	cout<<"删除T中的某个结点"<<endl;
    cout<<"输入所要删除的结点:";
	cin>>e;
    cout<<"输入LR的值（0或1）:";
	cin>>LR;
	DeleteChild(T,e,LR);
       cout<<"删除结点e的左或右子树后的二叉树为："<<endl;
	  PreOrderTraverse(T,printElement);
	
     cout<<"创建一个二叉树 c(c 无右子树):";
      CreateBiTree(c);
   cout<<"在结点e处插入一棵无右子树的二叉树c"<<endl;
	cout<<"输入所插结点："<<endl;
	 cin>>e;
	 cout<<"输入LR的值：";
     cin>>LR;
	 
	InsertChild(T,e,LR,c);
     cout<<"插入二叉树c后的二叉树为："<<endl;
	  PreOrderTraverse(T,printElement);

	cout<<"销毁二叉树(1代表已销毁，0代表未销毁)"<<endl;
	  cout<<DestroyBiTree(T)<<endl;
   
 }