二叉非递归的中序遍历（递归创建）

二叉链表的存储结构，创建二叉树，利用栈实现非递归中序遍历。

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define MaxSize 100
typedef struct BiNode
{
	int data;
	BiNode *lchild;
	BiNode *rchild;
}BiNode, *BiTree;
typedef struct
{
	BiNode *a[MaxSize];
	int top;
}SqStack;
int TreeCreated = 0;
int CreatTree(BiTree *T);
void NrInOrder(BiTree T);
void Push(SqStack *s, BiNode *x);
BiNode *Pop(SqStack *s);
int main()
{
	int choice = 0, flag;
	int leave = 0;
	BiNode *BT;
	printf("/n----------利用栈实现非递归遍历演示程序-----------/n");
	do
	{
		printf("1.创建一个二叉树，按先序遍历结果输入，空用0表示/n");
		printf("2.中序遍历二叉树，非递归方式遍历二叉树/n");
		printf("0.Quit/n");
		printf("-----Input your selection:");
		scanf("%d", &choice);
		switch(choice)
		{
		case 1:
			if(TreeCreated)
			{
				printf("sorry, the tree has been already created!/n");
				break;
			}
			printf("please put in number:/n");
			flag = CreatTree(&BT);
			if(flag == 1)
			{
				printf("ok, the tree named BT is created/n");
				TreeCreated = 1;
			}
			break;
		case 2:
			printf("In NrOrder:");
			NrInOrder(BT);
			break;
		case 0:
			leave = 1;
			break;
		}
	}while(!leave);
	printf("thanks for using, byebye!/n");
	return 0;
}
int CreatTree(BiTree *T)
{
	int ch = 0;
	scanf("%d", &ch);
	if(ch == 0) (*T) = NULL;
	else
	{
		(*T) = (BiTree) malloc (sizeof(BiNode));
		(*T)->data = ch;
		CreatTree(&(*T)->lchild);
		CreatTree(&(*T)->rchild);
	}
	return 1;
}
void NrInOrder(BiTree T)
{
	SqStack s;
	BiNode *p;
	s.top = 0;
	Push(&s, T);
	while(s.top != 0)
	{
		while(s.a[s.top] != NULL)
		{
			p = s.a[s.top];
			Push(&s, p->lchild);
		}
		p = Pop(&s);
		if(s.top != 0)
		{
			p = Pop(&s);
			printf("%3d", p->data);
			Push(&s, p->rchild);
		}
	}
	printf("/n");
}
void Push(SqStack *s, BiNode *x)
{
	if(s->top == MaxSize) printf("/nstack overflow!");
	else
	{
		s->top++;
		s->a[s->top] = x;
	}
}
BiNode *Pop(SqStack *s)
{
	BiNode *x;
	if(s->top == 0)
	{
		printf("/n stack underflow!");
		return NULL;
	}
	else
	{
		x = s->a[s->top];
		s->top--;
		return (x);
	}
}