#include <stdio.h>
#include <iostream>
#include <queue>
#include <stack>
#include <malloc.h>
#define SIZE 100

using namespace std;

typedef struct  BiTNode      //定義二叉樹節點結構
{
 char  data;                     //數據域
 struct BiTNode *lchild,*rchild; //左右孩子指針域
}BiTNode,*BiTree;

int visit(BiTree t);
void CreateBiTree(BiTree &T);    //生成一個二叉樹
void PreOrder(BiTree);          //遞歸先序遍歷二叉樹
void InOrder(BiTree);           //遞歸中序遍歷二叉樹
void PostOrder(BiTree);         //遞歸后序遍歷二叉樹
void InOrderTraverse(BiTree T); //非遞歸中序遍歷二叉樹
//主函數
main()
{
 BiTree T;       
 char j;
 int flag=1;
 //---------------------程序解說-----------------------
 printf("本程序實現二叉樹的操作。\n");
 printf("葉子結點以*表示。\n");
 printf("可以進行建立二叉樹，遞歸先序、中序、后序遍歷，非遞歸中序遍歷等操作。\n");
 //----------------------------------------------------
 printf("\n");
 printf("請建立二叉樹。\n");
 printf("建樹將以三個空格后回車結束。\n");
 printf("例如:1*2*3*4*5*6***(回車)\n"); CreateBiTree(T);       //初始化隊列
 getchar();
 while(flag)
    {
  printf("\n");
  printf("請選擇: \n");
  printf("1.遞歸先序遍歷\n");
  printf("2.遞歸中序遍歷\n");
  printf("3.遞歸后序遍歷\n");
  printf("4.非遞歸中序遍歷\n");
  printf("0.退出程序\n");
  scanf(" %c",&j);
  switch(j)
  {
   case '1':if(T)
            {
    printf("遞歸先序遍歷二叉樹:");
    PreOrder(T);
    printf("\n");
             }
   else printf("二叉樹為空!\n");
   break;
   case '2':if(T)
            {
    printf("遞歸中序遍歷二叉樹:");
    InOrder(T);
    printf("\n");
            }
   else printf("二叉樹為空!\n");
   break;
   case '3':if(T)
            {
    printf("遞歸后序遍歷二叉樹:");
    PostOrder(T);
    printf("\n");
            }
   else printf("二叉樹為空!\n");
   break;
   case '4':if(T)
            {
    printf("非遞歸中序遍歷二叉樹:");
    InOrderTraverse(T);
    printf("\n");
            }
   else printf("二叉樹為空!\n");
   break;
   default:flag=0;printf("程序運行結束，按任意鍵退出!\n");
  }
    }

}

//建立二叉樹
void CreateBiTree(BiTree &T)
{
 char ch;
 scanf("%c",&ch);    //讀入一個字符   
 if(ch=='*') T=NULL;
 else 
 {
  T=(BiTNode *)malloc(sizeof(BiTNode)); //生成一個新結點
  T->data=ch;
  CreateBiTree(T->lchild);  //生成左子樹
  CreateBiTree(T->rchild);  //生成右子樹
     }
}

//先序遍歷的遞歸
void PreOrder(BiTree T)
{
 if(T)
 {
  printf("%c ",T->data);  //訪問結點
  PreOrder(T->lchild);   //遍歷左子樹
  PreOrder(T->rchild);   //遍歷右子樹
 }
}

//中序遍歷的遞歸
void InOrder(BiTree T)
{
 if(T)
 {
  InOrder(T->lchild);   //遍歷左子樹 
  printf("%c ",T->data); //訪問結點
  InOrder(T->rchild);   //遍歷右子樹
 }
}

//后序遍歷的遞歸
void PostOrder(BiTree T)
{
 if(T)
 {
  PostOrder(T->lchild); //遍歷左子樹
  PostOrder(T->rchild); //訪問結點
  printf("%c ",T->data); //遍歷右子樹
 }
}

//非遞歸中序遍歷   
void InOrderTraverse(BiTree T)
{
 stack<BiTree> S;
 BiTree p;
 S.push(T);//跟指針進棧
 while(!S.empty())
 {
  p=new BiTNode;
  while((p=S.top())&&p)
   S.push(p->lchild);//向左走到盡頭
  S.pop(); //空指針退棧
  if(!S.empty())
  {
   p=S.top();
   S.pop();
   cout<<p->data<<"  ";
   S.push(p->rchild);
  }
 }

}
int visit(BiTree T)
{
 if(T)
 {
  printf("%c ",T->data);
  return 1;
 }
 else
  return 0;
}
/*二叉鏈表的前序生成原則是  
1輸入根結點值  
2若左子樹不為空,則輸入左子樹,否則輸入一個結束符, 
3若右子樹不為空,則輸入右子樹,否則輸入一個結束符*/