二叉樹的中序非遞歸周遊

中序周遊的非遞歸算法描述如下：

• 從根節點開始檢索，如果目前節點不為空，則将目前節點入棧，讓目前節點成為其左孩子節點，再繼續上一步的操作
• 加入目前節點為空了，說明其父節點已經沒有左孩子了，那麼将棧頂元素出棧并輸入
• 判斷棧頂元素是否有右孩子，如果有右孩子，則停止依次繼續出棧的操作，并檢索它的右孩子，重複第一步；如果沒有右孩子，則繼續将棧頂元素出棧
• 當棧為空，并且目前節點為空時，周遊完成，退出；

#include<stdio.h>
#include<stdlib.h>
typedef struct BTreeNode
{
	int data;
	struct BTreeNode *left;
	struct BTreeNode *right;
}BTreeNode,*BTree;
typedef struct stack
{
	BTree * data;
	int top;
	int size;
}stack;

InitStack(stack *s)
{
	s->top=0;
	s->size=0;
	s->data=(BTree *)malloc(sizeof(BTree));
}
Push(stack *s,BTree t)
{
   s->size++;
   realloc(s->data,sizeof(BTree)*(s->size));
   s->data[s->top++]=t;
}
BTree Pop(stack *s)
{
	if(s->size<=0) 
	{
		printf("the stack is empty!\n");
		return NULL;
	}
	s->size--;
	return s->data[--s->top];
}
BTree BuildTree()
{
	int data;
	BTree root=NULL;
	scanf("%d",&data);
	if(data!=-1)
	{
		root=(BTree)malloc(sizeof(BTreeNode));
		root->data=data;
		root->left=BuildTree();
		root->right=BuildTree();
	}
	return root;
}
void InOrder(BTree root)//中序遞歸周遊 
{
	if(root!=NULL)
	{
		InOrder(root->left);
		printf("%d ",root->data);
		InOrder(root->right);
	}
}
void InOrder_NoRecursion (BTree root)//中序非遞歸周遊 
{
	BTree t=root;
	stack s;
	InitStack(&s);//初始化棧 
 while(t!=NULL||s.size!=0)
 {
	while(t!=NULL)
	{
	Push(&s,t);
	t=t->left;
    }
    
    while(s.size!=0)
    {
    t=Pop(&s);
    printf("%d ",t->data);
    t=t->right;
    if(t!=NULL)  break;
    }   
 }  
}
main()
{
	printf("請以先序方式建立二叉樹:\n"); 
	BTree root=BuildTree();
	printf("中序遞歸周遊二叉樹的結果為:\n"); 
	InOrder(root);
	printf("\n中序非遞歸周遊二叉樹的結果為:\n"); 
	InOrder_NoRecursion(root);
}