/*=================================================*/
/*程序名稱：BTree_Inorder_NoRecursion_Traverse.cpp */
/*程序目的：函數(shù)實(shí)現(xiàn)                               */
/*Written by :Wang Qiang.                          */
/*=================================================*/
#include "BTree_Postorder_NoRecursion_Traverse.h"
#include <stdio.h>
#include <stdlib.h>

#define INIT_SIZE 100
#define STACKINCREMENT 10


/*--------------------------------------------*/
/*使用遞歸方式建立二叉樹                      */
/*--------------------------------------------*/

b_tree create_btree(int *nodelist, int position)
{
	b_tree newnode;

	if (nodelist[position] == 0 || position > 15) //遞歸終止條件
		return NULL;
	else
	{
		newnode=(b_tree) malloc (sizeof(treenode));
		newnode->data=nodelist[position];
		newnode->left=create_btree(nodelist,2*position);
		newnode->right=create_btree(nodelist,2*position+1);
		return newnode;
	}
}

/*--------------------------------------------*/
/*二叉樹中序遍歷打印節(jié)點(diǎn)的內(nèi)容                */
/*--------------------------------------------*/
void inorder_print_btree(b_tree point)
{
	if ( point!=NULL)
	{
		inorder_print_btree(point->left);
		printf("【%2d】",point->data);
		inorder_print_btree(point->right);
	}
}

/*--------------------------------------------------------*/
/*初始化棧                                                */
/*--------------------------------------------------------*/
void InitStack(TrStack &S)
{
	S.base=(b_tree *)malloc(INIT_SIZE*(sizeof(b_tree)));
	if(!S.base)
		printf("棧分配失敗\n");
	S.top=S.base;
	S.stacksize=INIT_SIZE;
}

/*--------------------------------------------------------*/
/*               判斷棧是否為空                           */
/*--------------------------------------------------------*/
int StackEmpty(TrStack S) 
{
	if(S.top==S.base)
		return 1;
	else 
		return 0;
}

/*--------------------------------------------------------*/
/*       取棧頂元素                                       */
/*--------------------------------------------------------*/
b_tree GetTop(TrStack S,b_tree &p)
{
	if(!StackEmpty(S))
	{
		p=*(S.top-1);
		return p;
	}
	else
		return NULL;
}

/*--------------------------------------------------------*/
/*壓棧                                                    */
/*--------------------------------------------------------*/
void Push(TrStack &S,b_tree node)
{
	if((S.top-S.base)>=S.stacksize)
	{
		S.base=(b_tree*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(b_tree));
		if(!S.base)
			printf("重新分配失敗\n");
		S.top=S.base+S.stacksize;
		S.stacksize+=STACKINCREMENT;
	}
	*S.top++=node;
	//if (node!=NULL)
		//printf("成功入棧:%d\n",node->data);
	//else
		//printf("空節(jié)點(diǎn)入棧\n");
}

/*--------------------------------------------------------*/
/*出棧                                                    */
/*--------------------------------------------------------*/
int Pop(TrStack &S,b_tree &p)
{
	if(S.top==S.base)
		return 0;
	p=*(--S.top);
	    return 1;
}

/*--------------------------------------------------------*/
/*              后序非遞歸遍歷二叉樹                      */
/*--------------------------------------------------------*/
void PostorderTraverse(b_tree T)
{
	TrStack S;
	InitStack(S);
	b_tree p=T;
	b_tree tag;

	while(p || !StackEmpty(S))
	{
		if (p)
		{
			Push(S,NULL);
			Push(S,p);
			p=p->left;
		}
		else
		{
			Pop(S,p);
			Pop(S,tag);

			if(tag==NULL)
			{
				Push(S,p);
				Push(S,p);
				p=p->right;
			}
			else
			{
				printf("%d",p->data);
				p=NULL;
			}
		}
	}
	
}