/*=================================================*/
/*程序名稱：BTree_Inorder_NoRecursion_Traverse.cpp */
/*程序目的：函數實現                               */
/*Written by :Wang Qiang.                          */
/*=================================================*/
#include "BTree_Inorder_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;
	}
}

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

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

/*--------------------------------------------------------*/
/*中序非遞歸遍歷二叉樹                                    */
/*--------------------------------------------------------*/
void InOrderTraverse(b_tree T)
{
	TrStack S;
	InitStack(S);
	b_tree p;
	Push(S,T); //將根節點入棧
	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); //將當前節點的右子樹的根節點壓棧
		}
	}
}