#include<stdio.h>
#include<malloc.h>

#define STACK_INIT_SIZE 10
#define STACKINCREMENT 5

typedef struct BiTNode						//樹結點
{
	char data;
	struct BiTNode *pLChild,*pRChild;
}BiTNode,*BiTree;

typedef struct								//堆棧
{
	BiTNode *base;
	BiTNode *top;
	int stacksize;
}*SqStack;

void InitStack(SqStack S)					//初始化
{
	S->base=(BiTNode *)malloc(STACK_INIT_SIZE*sizeof(BiTNode));
	if(!S->base) exit(0);
	S->top=S->base;
	S->stacksize=STACK_INIT_SIZE;
}

int StackEmpty(SqStack S)
{
	if(S->base==S->top) return 1;
	return 0;
}

void push(SqStack S,BiTNode *e)				//壓棧
{
	if(S->top-S->base>=S->stacksize)        //空間不足
	{
		S->base=(BiTNode *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(BiTNode));
		S->stacksize+=STACKINCREMENT;
	}
	if(e)									//將數據存入堆棧中
	{
		S->top->data=e->data;
		S->top->pLChild=e->pLChild;
		S->top->pRChild=e->pRChild;
	}
	else									//空指針存入無效數據
	{
		S->top->data='*';
	}
	S->top++;

}

BiTNode *pop(SqStack S)						//彈出節點
{
	BiTNode *t;

	t=(BiTNode *)malloc(sizeof(BiTNode));	//開BiTNode指針用于儲存彈出節點

	if(S->top==S->base) exit(0);			//棧空
	--S->top;
	if(S->top->data!='*')					//堆棧存有有效數據
	{
		t->data=S->top->data;				//用t來接收
		t->pLChild=S->top->pLChild;
		t->pRChild=S->top->pRChild;
		return t;
	}
	else									//堆棧存為無效數據
	{
		return S->top;						//彈出無效數據
	}
}

BiTNode *GetTop(SqStack S)					//返回堆棧的第一個節點
{
	if(S->top==S->base) 
	{
		return NULL;	
	}
	return (S->top-1);
}

BiTree CreatBiTree()						//建立二叉樹
{
	char ch;
	BiTree T;

	printf("請輸入節點數據：\n");
	scanf("%c",&ch);						//讀結點數據
	getchar();								//取回車符
			
	if(ch=='*') T=NULL;						//如果為*說明該指針為空
	else
	{
		if(T=(BiTree)malloc(sizeof (BiTNode)))
		{
			T->data=ch;						
			
			T->pLChild=CreatBiTree();		//同理建立左叉樹
			T->pRChild=CreatBiTree();
		}
	}
	return T;								//返回樹指針
}

void Visit(char e)							//打印數據
{
	printf("%c",e);
}

void PostOrderTraverse(BiTree T)			//后序遍歷
{
	SqStack S;
	BiTNode *p,*q;

	S=(SqStack)malloc(sizeof(SqStack));
	p=NULL;

	InitStack(S);
	push(S,T);
	while(!StackEmpty(S))
	{
		p=GetTop(S);
		while(p->data!='*')					//到左下位置
		{
			push(S,p->pLChild);
			p=GetTop(S);
		}
		q=pop(S);							//無效數據出棧
		if(((S->top-1)!=S->base)||((S->top-1)->pRChild))//剩余結點多余一個或者右結點非空
		{
			if((S->top-1)->pRChild)			//右結點存在
			{
				push(S,(S->top-1)->pRChild);//右結點入棧
				if(!(((S->top-1)->pRChild)||((S->top-1)->pLChild)))//入棧結點無左右孩子
				{
					q=pop(S);				//出棧
					Visit(q->data);			
					(S->top-1)->pRChild=NULL;//將其父結點的右孩子置空
				}
			}
			else							//左右節點都不存在
			{
				q=pop(S);				
				Visit(q->data);
				if((S->top-1)->pRChild->data==q->data)//該出棧結點位于樹中的右子樹
				{
					(S->top-1)->pRChild=NULL;//將其父節點的右孩子置空			
				}
				else
				(S->top-1)->pLChild=NULL;	//否則左孩子置空
			}
		}
		else								//剩下一個節點		 
		{
			q=pop(S);
			Visit(q->data);
		}
	}
}

int main()
{
	BiTree Tree;

	Tree=NULL;

	Tree=CreatBiTree();
	PostOrderTraverse(Tree);
}