先序遍历的非递归实现.c

二叉数先序循环的非递归实现

#include "malloc.h"
#define NULL 0
#define Max 50
#include "stdio.h"
typedef struct bitnode
{
	char data;
	struct bitnode *lchild;
	struct bitnode *rchild;
}BitNode,*BiTree;
BiTree CreatTree()
{
	char ch;BiTree q[Max],bt,s;int front,rear;
	bt=NULL;front=1;rear=0;
	scanf("\n%c",&ch);
	while(ch!='#')
	{
		s=NULL;
		if(ch!='0')
		{
			s=(BitNode*)malloc(sizeof(BitNode));
			s->data=ch;
			s->lchild=NULL;
            s->rchild=NULL;
		}
		rear++;
		q[rear]=s;
		if(rear==1)
			bt=s;
		else 
		{
			if(s!=NULL&&q[front]!=NULL)
				if(rear%2==0)
					q[front]->lchild=s;
				else q[front]->rchild=s;
				if(rear%2==1) front++;
		}
	scanf("\n%c",&ch);
	}
	return bt;
}
void Visit(char data)
{
	printf("  %c  ",data);
}
void Preorder(BiTree bt)
{
	BiTree Stack[Max],p;
	int top=0;
	p=bt;
	while(p!=NULL||top!=0)
	{
		while(p!=NULL)
		{
			Visit(p->data);
	    	top++;Stack[top]=p->rchild;
	    	p=p->lchild;
		}
        p=Stack[top];top--;
	}
}
void main()
{
	BiTree bt;
	printf("\n按照完全二叉树格式输入字符型结点值,按回车输入,空值为0，以'#'结束\n");
	bt=CreatTree();
	printf("\n先序遍历\n");
	Preorder(bt);
	printf("\n");
}