二叉树非递归遍历

今天看搜索算法的时候突然想到自己以前写的程序，优盘搞丢了。好多程序都不见了，看见笔记本还有一些有用的东东，备份下。

 

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
typedef struct BTREE
{
	char data;
	struct BTREE *lchild,*rchild;
}BTREE;
BTREE* queue[100];
int i,j;
BTREE *creat()
{
	BTREE *T;
	char ch;
	ch=getchar();
	if(ch=='#')
		T=NULL;
	else
	{
		T=(BTREE *)malloc(sizeof(BTREE));
		T->data=ch;
		T->lchild=creat();
		T->rchild=creat();
	}
	return T;
}
void initQueue(int n)
{
	for(int i=0;i<n;i++)
	{
		queue[i]=NULL;
	}
	return;
}
void DLR(BTREE *T)
{
	initQueue(100);
	if(!T)
		return ;
	while(1)
	{
		while(T)
		{
			printf("%3c",T->data);
			if(T->rchild)
				queue[++i]=T->rchild;
			T=T->lchild;
		}
		if(i)
		{
			T=queue[i];
			i--;
		}
		else
		{
	       puts("");
		   return;
		}
	}
}
void LDR(BTREE *T)
{
	initQueue(100);
	if(!T)
		return ;
	while(1)
	{
		while(T)
		{
			i++;
			queue[i]=T;
			T=T->lchild;
		}
		if(i)
		{
			T=queue[i];
			i--;
			printf("%3c",T->data);
			T=T->rchild;
		}
		else
		{
	       puts("");
			return;
		}
	}	
}
void LRD(BTREE *T)
{
	initQueue(100);
	if(!T)
		return ;
 while(1)
 {
	BTREE *pre;
	while(T)
	{
		i++;
		queue[i]=T;
		T=T->lchild;
	}
	pre=T;
	 while(i)
	 {
		T=queue[i];
		if(T->rchild==pre)
		{
			printf("%3c",T->data);
			pre=T;
			i--;
		}
		else
		{
			T=T->rchild;
			break;
		}
	 }
	if(!i)
		{
			puts("");
			return;
		}
 }
}
void LEVAL(BTREE *T)
{
	initQueue(100);
	if(!T)
		return ;
	queue[j]=T;
	while(queue[j])
	{
		if(T->lchild)
		queue[++i]=T->lchild;
		if(T->rchild)
		queue[++i]=T->rchild;
		printf("%3c",T->data);
		T=queue[++j];
	}
	puts("");
}	
int main()
{
	BTREE *T;
	T=creat();
	printf("前序输出：");
	DLR(T);
	printf("中序输出：");
	LDR(T);
	printf("后序输出：");
	LRD(T);
	printf("层次输出：");
         LEVAL(T);
         return 0;
}