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

typedef struct BiTNode
{
	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;
		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壓棧
		printf("%c",T->data);
		T=T->lchild;		//往左下方走一步
	}
	printf("%c",T->data);
	return T;
}


void main()	//先序遍歷的非遞歸算法的主程序
{										
	BiTree t;
	printf("請按先序擴展序列輸入二叉樹,空用*表示\n");
	CreateBiTree(t);
	printf("先序遍歷的非遞歸算法");
	stack *S;
	S=CreateStack();
	t=GoLeft(t, S);				// 找到最左下的結點
	while(t)							//t非空時
	{ 
		if (t->rchild)					//如果右子樹非空，則走到右子樹的最左端
		{
			t=t->rchild;
			t=GoLeft(t, S);
		}
		else if (!(S->top==S->base))		// 棧不空時退棧
			{
				t = pop(S);					//右子樹為空時，彈出雙親節點
			}
			else
		{
			t = 0;						// 棧空表明遍歷結束
		}
	} 
	printf("\n");
}