//* * * * * * * * * * * * * * * * * * * * * * * * * * *  
//*CHAPTER          :4  (4_2)                         *
//*PROGRAM          :非遞歸遍歷二叉樹                 *
//*CONTENT          :建立，先序、中序、后序遍歷二叉樹 *
//* * * * * * * * * * * * * * * * * * * * * * * * * * *
#include <dos.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#define MAX 100          //定義堆棧最大容量
enum BOOL{False,True};
enum RVISIT{Rchildnovisit,Rchildvisit};  
         //在后序遍歷二叉樹時用來指示是否已訪問過右子樹
typedef struct  BiTNode      //定義二叉樹節點結構
{char  data;                     //數據域
 struct BiTNode *lchild,*rchild; //左右孩子指針域
}BiTNode,*BiTree;
typedef struct        //定義堆棧結構
{BiTree elem[MAX];   //棧區
 int top;          //棧頂指針
}BiTreeStack;
void Initial(BiTreeStack &);     //初始化一個堆棧
BOOL Push(BiTreeStack &,BiTree); //將一個元素入棧
BOOL Pop(BiTreeStack&,BiTree &); //將一個元素出棧
BOOL Gettop(BiTreeStack ,BiTree &); //取得堆棧棧頂元素 
BOOL StackEmpty(BiTreeStack);    //判斷堆棧是否已空
void CreateBiTree(BiTree &);    //生成一個二叉樹
void PreOrder(BiTree);          //先序非遞歸遍歷二叉樹
void InOrder(BiTree);           //中序非遞歸遍歷二叉樹
void PostOrder(BiTree);         //后序非遞歸遍歷二叉樹
void main()
{BiTree T;
 char ch,j;
 int flag=1;
 BOOL temp;
 textbackground(3);  //設定屏幕顏色
 textcolor(15);
 clrscr();
 //--------------------程序解說-----------------
 printf("本程序實現二叉樹的非遞歸遍歷操作。\n");
 printf("可以實現建立二叉樹，非遞歸先序、中序、后序遍歷二叉樹\n");
 //---------------------------------------------
 printf("請將先序遍歷二叉樹的結果輸入以建立二叉樹。\n");
 printf("對于葉子結點以空格表示。\n");
 printf("例如:abc  de g  f   (回車)，建立如下二叉樹：\n");
 printf("           a      \n");
 printf("          /       \n");
 printf("         b        \n");
 printf("        / \\       \n");
 printf("       c   d      \n");
 printf("          / \\     \n");
 printf("         e   f    \n");
 printf("          \\       \n");
 printf("           g      \n");
 CreateBiTree(T);       //生成一棵二叉樹
 getchar();
 while(flag)
    { printf("請選擇: \n");
      printf("1.非遞歸先序遍歷\n");
      printf("2.非遞歸中序遍歷\n");
      printf("3.非遞歸中序遍歷\n");
      printf("4.退出程序\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;
	 default:flag=0;printf("程序運行結束，按任意鍵結束!\n");
	}
    }
 getch();
}

void Initial(BiTreeStack &S)
{S.top=-1;   //棧頂指針初始化為-1
}

BOOL Push(BiTreeStack &S,BiTree ch)
{//將元素ch入棧，成功返回True,失敗返回False
 if(S.top>=MAX-1) return False;//判斷是否棧滿
 else {S.top++;               //棧頂指針top加一
       S.elem[S.top]=ch;      //入棧
       return True;
      }
}

BOOL Pop(BiTreeStack &S,BiTree &ch)
{//將棧頂元素出棧,成功返回True，并用ch返回該元素值，失敗返回False
 if(S.top<=-1) return False;//判斷是否棧空
 else {S.top--;                                //棧頂指針減一
       ch=S.elem[S.top+1];
       return True;
      }
}
BOOL Gettop(BiTreeStack S,BiTree &ch)
{//取得棧頂元素，成功返回True，并用ch返回該元素值，失敗返回False
 if(S.top<=-1)
    return False;
 else {ch=S.elem[S.top];//顯示棧頂元素
       return True;
      }
}

BOOL StackEmpty(BiTreeStack S)
{//判斷堆棧是否已空，若空返回True,不空返回False
 if(S.top<=-1) return True;
 else return False;
}
void CreateBiTree(BiTree &T)
{//生成一棵二叉樹，該二叉樹以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)
{//先序非遞歸遍歷以T為根結點的二叉樹
 BiTreeStack S;
 BiTree p;
 Initial(S);
 p=T;
 while(p||!StackEmpty(S))
    { if(p) {printf("%c",p->data);
	     Push(S,p);
	     p=p->lchild;
	    }
      else {Pop(S,p);
	    p=p->rchild;
	   }
    }
 printf("\n");

}
void InOrder(BiTree T)
{//中序非遞歸遍歷以T為根結點的二叉樹
 BiTreeStack S;
 BiTree p;
 Initial(S);
 p=T;
 while(p||!StackEmpty(S))
    { if(p) {Push(S,p); p=p->lchild;}
      else {Pop(S,p);
	    printf("%c",p->data);
	    p=p->rchild;
	   }
    }
 printf("\n");
}
void PostOrder(BiTree T)
{//后序非遞歸遍歷以T為根結點的二叉樹
 BiTreeStack S;
 BiTree p,q;
 RVISIT tag;
 Initial(S);
 p=T;
 do {
    while(p)
      {Push(S,p); p=p->lchild;}
    q=NULL; tag=Rchildvisit;
    while(!StackEmpty(S)&&tag)
      {Gettop(S,p);
       if(p->rchild==q)
	   {printf("%c",p->data);
	    Pop(S,p);
	    q=p;
	   }
       else {p=p->rchild; tag=Rchildnovisit;}
      }
   }while(!StackEmpty(S));
 printf("\n");
}