二叉树的层次遍历

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

typedef struct BTNode{
char data;
struct BTNode *lchild,*rchild;
}BTNode,*BiTree;

#define MAXSIZE 100
typedef struct Queue{
BiTree *base;
int front;
int rear;
}SqQueue;

void CreatBiTree(BiTree &bt){
//创建二叉树
char ch = getchar();
if(ch == '#')
bt = NULL;
else{
bt = (BiTree)malloc(sizeof(BTNode));
if(!bt){
printf("创建二叉树时，申请结点出错！\n");
exit(0);
}
bt->data = ch;
CreatBiTree(bt->lchild);
CreatBiTree(bt->rchild);
}
}//CreatBiTree
void InitQueue(SqQueue &q){
//初始化一个队
q.base = (BiTree *)malloc(MAXSIZE * sizeof(BiTree));
if(!q.base){
printf("初始化失败!\n");
exit(0);
}
q.front = q.rear = 0;
}//InitQueue

void EnQueue(SqQueue &q,BiTree bt){
//数据进队
if((q.rear + 1)%MAXSIZE == q.front){
printf("此时队满！\n");
}
q.base[q.rear] = bt;
q.rear = (q.rear + 1)%MAXSIZE;
}//EnQueue

int QueueEmpty(SqQueue q){
//判断队列是否满
if(q.front == q.rear)
return 1;
return 0;
}//QueueEmpty

void DeQueue(SqQueue &q,BiTree &bt){
//数据出队
if(QueueEmpty(q)){
printf("队空，没有数据出队\n");
exit(0);
}
bt = q.base[q.front];
q.front =(q.front + 1)%MAXSIZE;

}//DeQueue


void LevelOrderTraverse(BiTree bt)
{//对二叉树进行层次遍历
Queue Q;
int count=0;
BiTree p;
if (bt)
{
InitQueue(Q); EnQueue(Q, bt);
while (!QueueEmpty(Q))
{
DeQueue(Q, p);
printf("%3c", p->data);
count++;
if (p->lchild)EnQueue(Q, p->lchild);
if (p->rchild)EnQueue(Q, p->rchild);

}
}
printf("结点数为：%d",count);
}//LevelOrderTraverse

void main(){
BiTree bt;
CreatBiTree(bt);
LevelOrderTraverse(bt);

}