//5.后序遍歷的非遞歸算法
#define STACK_INIT_SIZE 100//存儲空間初始分量
#define STACKINCREMENT 10//存儲空間分配增量
#include<stdio.h>
#include<stdlib.h>
#include<iostream.h>
   typedef struct BTNode
   { //定義樹的存儲結構
	 char data;
     BTNode *lchild,*rchild;}* BTree;
   typedef struct 
   {  //定義棧的存儲結構
	  BTree *base, *top;
	  int *ibase, mark, stacksize;	
   }SqStack;
   int CreateBTree(BTree &BT)
   {  //按先序建立二叉樹
	   char ch=' ';scanf("%c",&ch);
	    if(ch==' ')BT=NULL;
	     else
		 {
		  if(!(BT=(BTree)malloc(sizeof(BTree))))return 0;	
		  BT->data=ch;
		  CreateBTree(BT->lchild);
		  CreateBTree(BT->rchild);
	}return 1;
   }
   void InitStack(SqStack &Sq)
   {   //初始化棧
	   Sq.base=(BTree *)malloc(STACK_INIT_SIZE*sizeof(BTree));
	   Sq.ibase=(int *)malloc(STACK_INIT_SIZE*sizeof(int));
	   Sq.top=Sq.base;
	   Sq.mark=0;
	   Sq.stacksize=STACK_INIT_SIZE;
   } 
   int StackEmpty(SqStack S)
   {//判空棧
	   if(S.top==S.base)return 1;
	   return 0;
   }
   void Push(SqStack &S,BTree e,int i)
   {  //入棧  
	   //(其中用i來選擇對樹的左或右子樹的操作)
	   if(S.top-S.base>=S.stacksize)
	   { S.base=(BTree *)realloc(S.base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(BTree));
		 S.top=S.base+S.stacksize;
		 S.stacksize+=STACKINCREMENT;
	   }
	   *(S.top)=e;   S.ibase[S.mark]=i;
	   S.mark++;     S.top++;
   }
   int Pop(SqStack &S,BTree *e,int &i)
   {   if(S.top==S.base)return 0;	
	   S.top--;         *e=*S.top;
	   S.mark--;        i=S.ibase[S.mark];	
	   return 1;
   }//出棧  (其中用i來選擇對樹的左或右子樹的操作)
   void houTraverse(BTree T)
   {  //后序非遞歸遍歷
	   SqStack s;      int i=0;
	   InitStack(s);   BTree p;
	   p=T;
	   Push(s,p,0);
	   while(!StackEmpty(s))
	   {Pop(s,&p,i);
	     switch(i)
		 {case 0:  Push(s,p,1);//i為0對左子樹操作
	               if(p->lchild)   Push(s,p->lchild,0); break;
    	  case 1:  Push(s,p,2);//i為1對右子樹操作
		           if(p->rchild)   Push(s,p->rchild,0); break;
		  case 2:  cout<<p->data;//i為2輸出
		 }
	   }
   }

   void main()
   {   BTree T;
	   cout<<"輸入結點的先序擴展序列:"<<endl;   CreateBTree(T);
	   cout<<"\n非遞歸后序遍歷為：";            houTraverse(T);
	   cout<<endl;
   }
  /*輸入結點的先序擴展序列:
   ab c  de  f
  非遞歸后序遍歷為：cbefda */