/*=============================================*/
/*程序名稱：Inorder_Traverse_NoRecursion.c    */
/*程序目的：非遞歸遍歷二叉樹                   */
/*Written by :Wang Qiang.                      */
/*=============================================*/
#include <stdio.h>
#include <stdlib.h>

#define INIT_SIZE 100
#define STACKINCREMENT 10
#define ERROR 0;

struct tree  //樹的結構
{
	struct tree *left;
	int data;
	struct tree * right;
};

typedef struct tree treenode; //新的樹類型
typedef treenode * b_tree;//樹類型指針

struct Stack
{
	b_tree *top; 
	b_tree *base;
	int stacksize;
};
typedef struct Stack TrStack;
/*--------------------------------------------*/
/*使用遞歸方式建立二叉樹                      */
/*--------------------------------------------*/

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;
	}
}

/*--------------------------------------------*/
/*二叉樹中序遍歷打印節點的內容                */
/*--------------------------------------------*/
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);
		//printf("%d",p->data);
		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("空節點入棧\n");
}


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


void InOrderTraverse(b_tree T) //非遞歸遍歷二叉樹
{
	TrStack S;
	InitStack(S);
	b_tree p;
	Push(S,T); //將根節點入棧
    //p=GetTop(S,p);
	//printf("%d",p->data);
	while(!StackEmpty(S))
	{
		while(GetTop(S,p))
		{
			Push(S,p->left);
		}
		Pop(S,p);
		if(!StackEmpty(S))
		{
			Pop(S,p);
			printf("%d",p->data);
			Push(S,p->right);
		}
	}
}

/*---------------------------------------------------*/
/*主程序                                             */
/*---------------------------------------------------*/
void main()
{
	b_tree root=NULL;
    
	int nodelist[16]={0,5,2,9,1,4,7,0,0,0,3,0,6,8,0,0};

	root=create_btree(nodelist,1);

	printf("The node content of the linklist binary tree is :\n");
	inorder_print_btree(root);
	printf("\n");
	//以上二叉樹建立完畢！下面是以非遞歸方式遍歷二叉樹
    printf("中序非遞歸遍歷二叉樹:");
	InOrderTraverse(root);
	printf("\n");
}