//用擴展二叉樹的先序序列建立二叉樹的二叉鏈表存儲結構，輸出二叉樹的先序，中序，后序和層序序列，
//交換二叉樹的所有結點的左，右子樹，再輸出二叉樹的先序，中序，后序和層序序列。 

#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#define NULL 0
#define MAXSIZE 100

typedef struct BiTNode
{	//建立二叉數的二叉鏈表存儲結構
		char data;
		struct BiTNode * lchild, * rchild;
}BiTNode,*BiTree;
typedef struct{
		BiTree base[MAXSIZE+1];
		int front;
		int rear;
		int length;
}SqQueue;

BiTree CreateBiTree(){	//創建一個二叉樹
		BiTree T;
		char ch;
		T=(BiTree)malloc(sizeof(BiTNode));

		ch=getchar();
		if(ch=='#')  T=NULL;//字符為空格時指針為空
		else{
		   T->data=ch;
			 T->lchild=CreateBiTree();//遞歸調用創建左子樹
			 T->rchild=CreateBiTree();//遞歸調用創建右子樹
				}
	    return T;
}

 void PreOrderTraverse(BiTree T){
	     if (T!= NULL)
	     {
	         cout<<T->data<<endl;
	
	         PreOrderTraverse(T->lchild);
	         PreOrderTraverse(T->rchild);
	     }
	        }
void MidOrderTraverse(BiTree T){
         if (T!=NULL)
         {
             MidOrderTraverse(T->lchild);
             cout<<T->data<<endl;
             MidOrderTraverse(T->rchild);
         }
        }
void PostOrderTraverse(BiTree T){
         if (T!=NULL)
       {
           PostOrderTraverse(T->lchild);
           PostOrderTraverse(T->rchild);
           cout<<T->data<<endl;
       }
        }
void InitQueue(SqQueue &Q){
		Q.front=Q.rear=0;
		Q.length=0;
}

void EnQueue(SqQueue &Q,BiTree e){
		 if((Q.rear + 1) % MAXSIZE ==Q.front)/*對尾下一個和對頭相等 (滿)*/
		       	 exit(0);
		  
		  Q.rear = (Q.rear + 1) % MAXSIZE;   /*數位加一*/ 
					     
 		 Q.base[Q.rear]=e;
}
/*DeQueue : 出隊列,返回一個BiTNode類型值*/ 
BiTNode * DeQueue(SqQueue & Q){
							     
	  if(Q.front ==Q.rear)/*/如果對尾和對頭相等 (空)*/
	   {
	       exit(0);
	  }
								     
      Q.front = (Q.front + 1) % MAXSIZE;/*進一位,注意,尾和頭都進*/
						     
	  return (Q.base[Q.front]);
}
bool IsQueueEmpty(SqQueue Q)
{
	 return (Q.front == Q.rear);
}
void HierarchyBiTree(BiTree T) { 
    	SqQueue Q; 		// 保存當前節點的左右孩子的隊列 
    	InitQueue(Q); 		// 初始化隊列 
		if (T == NULL) exit(0); //樹為空則返回 
		BiTNode* p = T; // 臨時保存樹根T到指針p中 
		cout<< p->data <<endl;	// 訪問根節點 
			
		if (p->lchild) EnQueue(Q, p->lchild); 	// 若存在左孩子，左孩子進隊列 
		if (p->rchild) EnQueue(Q, p->rchild); 	// 若存在右孩子，右孩子進隊列 
		while (!IsQueueEmpty(Q)) { 	// 若隊列不空，則層序遍歷 
			    p=DeQueue(Q); 			// 出隊列 
				cout<<p->data<<endl; 	// 訪問當前節點 
			    if (p->lchild) EnQueue(Q, p->lchild); 	// 若存在左孩子，左孩子進隊列 
				if (p->rchild) EnQueue(Q, p->rchild);  // 若存在右孩子，右孩子進隊列 
								} 
			
	  				
						}
  

void Exchange(BiTree &T)
{							
		BiTNode* p ;				
		
		if (T!=NULL){
						 	
			p=T->lchild;
		    T->lchild=T->rchild;
			T->rchild=p;
			Exchange(T->lchild);
			Exchange(T->rchild);
			 }
}
void main()
{
				BiTree T;
				cout<<"先序建立二叉樹"<<endl;
				T=CreateBiTree();
				cout<<"先序序列："<<endl;
				PreOrderTraverse(T);
				cout<<"中序序列："<<endl;
				MidOrderTraverse(T);
				cout<<"后序序列："<<endl;
				PostOrderTraverse(T);
				cout<<"層次遍歷序列："<<endl;
				HierarchyBiTree(T);
				cout<<"交換左右子樹"<<endl;
				Exchange(T);
				cout<<"先序序列："<<endl;
				PreOrderTraverse(T);
				cout<<"中序序列："<<endl;
				MidOrderTraverse(T);
				cout<<"后序序列："<<endl;
				PostOrderTraverse(T);
				cout<<"層次遍歷序列："<<endl;
				HierarchyBiTree(T);
				
				
}