学步园

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define maxnum 100
#define maxitem 1024
typedef struct node
{
	char data;
	struct node *lchild,*rchild;
}btree;
typedef btree* QElemType;

//队列元素
typedef struct QNode
{
	QElemType data;
	struct QNode *next;
}QNode,*QueuePtr;

//队列
typedef struct 
{
	QueuePtr front,rear;
}LinkQueue;

btree *Q[maxnum];
btree *CreatTree(char str[])
{
	int i=0;
	int front=1,rear=0;
	btree *root,*s;
	root = NULL;	//树根
	while(str[i] != '#')		//如果遇到#意味着输入结束
	{
		s = NULL;
		if(str[i] != '@')		//@符号代表NULL
		{
			s = (btree*)malloc(sizeof(btree));
			s->data = str[i];
			s->lchild = NULL;
			s->rchild = NULL;
		}
		rear ++;
		Q[rear] = s;
		if(rear == 1)root = s;
		else
		{
			if(s && Q[front])
			if(rear % 2 == 0)
				Q[front]->lchild = s;
			else
				Q[front]->rchild = s;
			if(rear % 2 == 1)front++;

		}
		i++;
	}

	return root;
}

//初始化队列
int InitQueue(LinkQueue *Q)
{
	(*Q).front = (*Q).rear = (QueuePtr)malloc(sizeof(QNode));
	if(!(*Q).front)exit(1);
	(*Q).front->next = NULL;
	return 1;
}

//判断队列是否为空
int QueueEmpty(LinkQueue Q)
{
	if(Q.front == Q.rear)return 1;
	else return 0;
}

//进入队列
int EnQueue(LinkQueue *Q,QElemType e)
{
	QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
	if(!p)exit(1);
	p->data = e;
	p->next = NULL;
	(*Q).rear->next = p;
	(*Q).rear = p;
	return 1;
}

//出队列
int DeQueue(LinkQueue *Q,QElemType *e)
{
	QueuePtr p;
	if((*Q).front == (*Q).rear)return 0;
	p = (*Q).front->next;
	*e = p->data;
	(*Q).front->next = p->next;

	if((*Q).rear == p)
		(*Q).rear = (*Q).front;
	free(p);
	return 1;
}

//层次遍历二叉树
void LevelOrderTree(btree *root)
{
	LinkQueue q;
	QElemType a;
	if(root)
	{
		InitQueue(&q);
		EnQueue(&q,root);
		while(!QueueEmpty(q))
		{
			DeQueue(&q,&a);
			printf("%c ",a->data);
			if(a->lchild != NULL)
				EnQueue(&q,a->lchild);
			if(a->rchild != NULL)
				EnQueue(&q,a->rchild);
		}

		printf("\n");
	}
}

//销毁树
void DestroyTree(btree *root)
{
	if(root == NULL)return ;
	if(root)
	{
		DestroyTree(root->lchild);
		DestroyTree(root->rchild);
	}
	free(root);
	root = NULL;
}
int main()
{
	btree *root;
	char str[maxitem];
	gets(str);
	strcat(str,"#");
	root = CreatTree(str);
	LevelOrderTree(root);
	DestroyTree(root);
	return 0;

}