#include <iostream.h>
typedef struct bitnode
{
	char data;
	struct bitnode *lchild,*rchild;
}bitnode ,*bitree;
//建立二叉樹二叉鏈表存儲
void createbitree(bitree *t)
{
	//以加入結點的先序序列輸入，構造二叉鏈表
	char ch;
	cin>>ch;
	if(ch=='0')//讀入0時，結點置空
		(*t)=NULL;
	else
	{
		(*t)=new bitnode;//生成結點空間
		(*t)->data=ch;
		createbitree(&(*t)->lchild); //左子樹
        createbitree(&(*t)->rchild);//右子樹
	}
}
//先序遍歷
void preorder(bitree bt)
{
	if(bt==NULL)
		return ;
	cout<<(bt->data)<<'\t';
	preorder(bt->lchild);
	preorder(bt->rchild);
}
//中序遍歷
void minorder(bitree bt)
{
	if(bt==NULL)
		return ;
	minorder(bt->lchild);
	cout<<(bt->data)<<'\t';
	minorder(bt->rchild);

}
//后序遍歷
void postorder(bitree bt)
{
	if(bt==NULL)
		return;
	postorder(bt->lchild);
	postorder(bt->rchild);
	cout<<(bt->data)<<'\t';


}
//按層遍歷
void levelorder(bitree bt)
{
	bitree queue[100];
	int front,rear;
	if(bt==NULL)
		return;
	front=-1;
	rear=0;
	queue[rear]=bt;
	while(front!=rear)
	{
		front++;
		cout<< (queue[front]->data)<<'\t';
		if(queue[front]->lchild!=NULL)
		{
			rear++;
			queue [rear]=queue[front]->lchild;


		}
		if(queue[front]->rchild!=NULL)
		{
			rear++;
			queue [rear]=queue[front]->rchild;
		}
	}
}

bitree exchange(bitree bt)//交換左右子樹
{
	if(bt==NULL)
		return NULL;
    bitree mt,nt;
	nt=bt->lchild;
	mt=bt;
	bt->lchild=mt->rchild;
	bt->rchild=nt;
	exchange(bt->lchild);
	exchange(bt->rchild);
	return bt;
}
void main()
{
   bitree bt,et;
   char a;
   while (1)
   {
   cout<<"                        歡迎使用二叉樹應用系統                    "<<endl;
   cout<<"                                         ————設計者：黃春亮   "<<endl;
    
	   cout<<"                        1.建立二叉樹"<<endl;
	   cout<<"                        2.遍歷二叉樹"<<endl;
	   cout<<"                        3.交換左右子樹"<<endl;
	   cout<<"                        4.退出二叉樹操作"<<endl;

   
   cin>>a;
   
   switch(a)
   {
   case '1':cout<<"請輸入節點元素(用0代替空)"<<endl;
	      createbitree(&bt);break;
   case'2':
	   { 
		   cout<<"          A.先序遍歷"<<endl;
		   cout<<"          B.中序遍歷"<<endl;
		   cout<<"          C.后序遍歷"<<endl;
           cout<<"          D.層次遍歷"<<endl;
		   char b;
	   cin>>b;
	   switch(b)
	   {
	   case 'A':
		   { cout<<"先序遍歷:"<<endl;
		    preorder(bt);
			cout<<endl;
		   }
		   break;
		   
	   case 'B':
		   {
            cout<<"中序遍歷:"<<endl;
            minorder(bt);
            cout<<endl;
		   }
		   break;
		   
	   case 'C':
		   {
            cout<<"后序遍歷:"<<endl;  
            postorder(bt);
            cout<<endl;
		   } 
			break;
		
	   case 'D':
		   	{
		      cout<<"按層遍歷:"<<endl;
		      levelorder(bt);
		      cout<<endl;
			}
			
	   }break;
	
   case '3':
	   {
            cout<<"交換左右子樹:"<<endl;  
            et=exchange(bt);
            cout<<"交換完成!"<<endl;
	   }
	   break;
		

   case '4':cout<<"謝謝使用"<<endl;return;
   }
	
}
}
}