#include<iostream> 
#define STACK_INIT_SIZE 100//棧或隊列的大小常量 
#define STACKINCREMENT 50  //用于擴增棧的大小 
using namespace std;
char preorder[100];   //存放二叉樹的前序序列 
char inorder[100];    //存放二叉樹的中序序列 
typedef struct BitNode{  //定義二叉鏈表的結構 
   char value;
   struct BitNode *lchild, *rchild;        
}BitNode ,* BitNodeptr;
typedef struct{   //定義一個存放二叉樹結點的棧 
     BitNode *top;
     BitNode *base;
     int stacksize;      
}Stack;
typedef struct{    // 定義一個存放二叉樹結點的隊列
     BitNode *front;
     BitNode *tail; 
     int Queuesize;       
}Queue;
void InitStack(Stack &S)//初始化棧 
{
   S.base=(BitNode*)malloc(STACK_INIT_SIZE*sizeof(BitNode));
   S.top=S.base;
   S.stacksize=STACK_INIT_SIZE;    
}
void InitQueue(Queue &S)  //初始化隊列 
{
   S.front=(BitNode*)malloc(STACK_INIT_SIZE*sizeof(BitNode));  
   S.tail=S.front;
   S.Queuesize=STACK_INIT_SIZE; 
}
void Pop(Stack &S,BitNodeptr &p) //取出棧頂元素，并把它賦給P 
{
   if(S.top>S.base){
      S.top--;
      p=(BitNode*)malloc(sizeof(BitNode));
      p->value=S.top->value;
      p->lchild=S.top->lchild;
      p->rchild=S.top->rchild;                  
   }     
}
void Dequeue(Queue &S,BitNodeptr &p)  //取出隊列的隊頭元素，并把它賦給P 
{
   if(S.front!=S.tail){
     p=(BitNode*)malloc(sizeof(BitNode));
     p->value=S.front->value;  
     p->lchild=S.front->lchild;
     p->rchild=S.front->rchild; 
     S.front++;
     } 
}
int QueueEmpty(Queue &S)             //判斷一個隊列是否為空 
{
   if(S.front==S.tail)
     return 1;
   else return 0;       
}
void Enqueue(Queue &S,BitNodeptr p)   //元素P進隊列 
{
   if((S.front-S.tail)%STACK_INIT_SIZE!=1){
      S.tail->value=p->value;
      S.tail->lchild=p->lchild;
      S.tail->rchild=p->rchild;
      S.tail++;                                          
   }       
}
void GetTop(Stack &S,BitNodeptr &p)   // 察看當前的棧頂元素 
{
   if(!p)p=(BitNode*)malloc(sizeof(BitNode));
   p->value=(S.top-1)->value;
   p->lchild=(S.top-1)->lchild;
   p->rchild=(S.top-1)->rchild;     
}
void Push(Stack &S,BitNodeptr p)//把元素P壓入棧中 
{
   if(S.top-S.base>=S.stacksize){
      S.base=(BitNode*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BitNode));    
      S.top=S.base+S.stacksize;    
      S.stacksize+= STACKINCREMENT;
   }
   S.top->value=p->value;
   S.top->lchild=p->lchild;
   S.top->rchild=p->rchild;
  
   S.top++;
}
int StackEmpty(Stack &S)  //判斷當前的棧是否為空 
{
   if(S.top==S.base)
     return 1;
   else return 0;     
}
void creatTree(BitNodeptr &current,int i, int start,int end)//根據前序序列和中敘序列構造一根二叉樹 
{
   if(start>end)
      current=NULL;             
   else{
      int k;  
      for(k=start;inorder[k]!=preorder[i];k++);
      current=(BitNode*)malloc(sizeof(BitNode));
      current->value=preorder[i];
      creatTree(current->lchild,i+1,start,k-1);
      creatTree(current->rchild,i+k-start+1,k+1,end);     
   }
}

void visit(BitNodeptr p)
{
   cout<<p->value;     //訪問結點P的值 
}

void findvertice(int &control,int n,int &m,char path[],BitNodeptr T,char A)//查找一條到所求結點的路徑，如果不存在該路徑，則 control為0 
{                                                                          //找到該路徑了就返回該路徑，并control為1 
     if(control==1)
        path[m]='\0';
     else if(T){
             path[n]=T->value;
             if(path[n]==A){control=1;m=n+1;}
             findvertice(control,n+1,m,path,T->lchild,A);
             findvertice(control,n+1,m,path,T->rchild,A);
          }       
}
void postorderTraverse(BitNodeptr T)  //后序遍歷二叉樹 
{   
    Stack S;
    InitStack(S);
    Push(S,T);
    T=T->lchild;
    BitNodeptr p;
    int flag;
    while(!StackEmpty(S)){
       while(T){Push(S,T);T=T->lchild;} 
       p=NULL;
       flag=1;
       while(!StackEmpty(S)&&flag){
          GetTop(S,T);                         
          if(!T->rchild||!p){
             if(T->rchild==p){
                visit(T);
                p=T;   
                Pop(S,T);              
             }  
             else{
                T=T->rchild;
                flag=0;     
             }      
          }
          else{
             if(T->rchild->value==p->value){
                 visit(T);
                 p=T;   
                 Pop(S,T);           
             }  
             else{
                T=T->rchild;
                flag=0;     
             }     
          }                                 
       }
                              
    }      
}
void levelTraverse(BitNodeptr T){//按層次遍歷二叉樹 
   
   BitNodeptr p;
   Queue S;
   InitQueue(S);
   if(T)Enqueue(S,T);
   
   while(!QueueEmpty(S)){
      Dequeue(S,p);
      visit(p);
      if(p->lchild) Enqueue(S,p->lchild);   
      if(p->rchild) Enqueue(S,p->rchild);                  
   }    
}

int main()
{
   cout<<"please input the preorder:"<<endl;//輸入前序序列 
   cin>>preorder;
   cout<<"please input the inorder:"<<endl;//輸入后序序列 
   cin>>inorder;
   
   int end;          //統計有多少個結點 
   for(end=0;preorder[end]!='\0';end++);
   
   BitNodeptr root;    //調用函數來建立一顆二叉樹 
   creatTree(root,0,0,end-1);
   
   cout<<"the postordertraverse is:"; //輸出所建二叉樹的后序遍歷序列 
   postorderTraverse(root);
   cout<<endl;
   
   cout<<"the leveltraverse is:";     //輸出所建二叉樹的按層次遍歷序列 
   levelTraverse(root);
   cout<<endl;
   
   cout<<"please input vertice you want to find:"<<endl;//輸入要尋找的結點 
   char A;
   char path[100];       //如果該結點存在樹中，就用path數組來記錄該路徑 
   int n=0,control=0,m=0;
   cin>>A;
   findvertice(control,n,m,path,root,A); //調用函數來判斷所求結點是否在樹中，并記錄下路徑 
   if(control==0)             //如果不存在該結點 
     cout<<"there is not the vertice"<<endl;
   else{                       //如果存在該結點 
     cout<<"the path in the tree is:"<<path[0];
     for(int i=1;path[i]!='\0';i++)
       cout<<"-->"<<path[i];  
   }
   system("pause");
   return 0;
}