#include <malloc.h>
#include <stdlib.h>
#include <stdio.h>	
#define NULL 0
#define OVERFLOW 0
#define STACKSIZE 50
#define ADD	20		

typedef struct BiTNode
{
	int sign;
	char data;
	struct BiTNode *lchild;
	struct BiTNode *rchild;		
}*BiTree;		

typedef struct stack
{
	BiTree *base;
	BiTree *top;
	int stacksize;		//規定堆棧的大小
}stack;


void CreateBiTree(BiTree &T)	//先序擴展序列建立二叉樹的遞歸算法 
{  
	char ch;
	scanf("%c",&ch);
	if (ch=='*') 
	{
		T=NULL;		
	}
	else 
	{ 
		if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))
		{
			exit(OVERFLOW);
		}
		T->data=ch;
		T->sign=0;
		CreateBiTree(T->lchild); 
		CreateBiTree(T->rchild); 
	}  
} 





stack* CreateStack()	//構造一個空棧
{
	stack *s=(stack*)malloc(sizeof(stack));
	if(!s)	exit(OVERFLOW);
	
	s->base=(BiTree*)malloc(STACKSIZE*sizeof(BiTree));
	if(!s->base) exit (OVERFLOW);
	
	s->top=s->base;
	s->stacksize=STACKSIZE;
	return s;
}


void push(stack *s, BiTree i)			//壓棧
{
	if(s->top-s->base>=s->stacksize)	//棧滿，追加存儲空間
	{
		s->base = (BiTree*)realloc(s->base,(s->stacksize+ADD)*sizeof(BiTree));
		if(!s->base)	exit(OVERFLOW);			
		s->top=s->base+s->stacksize;
		s->stacksize=s->stacksize+ADD;
	}
	*(s->top)=i;
	(s->top)++;
}


BiTree pop(stack *s)	//出棧
{
	BiTree i;
	if(s->top==s->base)
	{
		return 0;
	}
	else
	{
		i=*(--s->top);
		return i;
	}
}


BiTree GoLeft(BiTree T, stack *S)
{					
	if (!T)				
	{
		return 0;
	}
	while (T->lchild)		//T->lchild非空
	{  
		push(S,T);			//把T壓棧
		T=T->lchild;		//往左下方走一步
	}
	return T;
}


void main()	//后序遍歷的非遞歸算法的主程序
{										
	BiTree t;
	printf("請按先序擴展序列輸入二叉樹,空用*表示\n");
	CreateBiTree(t);
	stack *S;
	printf("\n后序非遞歸遍歷二叉樹的結果：");
	
	S=CreateStack();
	t=GoLeft(t, S);				// 找到最左下的結點
	while(t)							//t非空時
	{ 
		if( (!(t->rchild))||(t->sign==1))					
		{
			printf("%c",t->data);
			
		}
		if ((t->sign==0)&&(t->rchild))		
			{
				t->sign=1;					
				push(S, t);
				t=t->rchild;
				t=GoLeft(t, S);
				
			}
			else if (!(S->top==S->base))		// 棧不空時退棧
				{
					t = pop(S);					
				}
				else
				{
					t = 0;	
				} 
	}printf("\n"); 
}