经过两天长时间的学习, 通过研究队列以及二叉树的相关性质，终于写出了二叉树的层次遍历。
该实现的核心就是使用队列，每次把访问到的节点的左右子树放到队列里面去，出队的时候同样操作！
感谢@原来如此 ， @AlexMok ，两位同学，在小组相互学习的过程中收获良多！
下面放出实现源码：
#include <stdlib.h>
#include <stdio.h>
#define MAXSIZE 20
/*********定义两个结构体*********/
typedef struct BTree
{
char data;
struct BTree *lchild;
struct BTree *rchild;
}BTree;
typedef struct CircleQueue
{
int num;
int front;
int rear;
BTree *p;
}CircleQueue;
/**********************************队列部分***********************************/
/**********初始化队列*****************/
CircleQueue * InitQueue()
{
CircleQueue *q = malloc(sizeof(CircleQueue));
q->p = malloc(MAXSIZE *(sizeof(BTree)));
q->front = q->rear = 0;
q->num = 0;
return q;
}
/**************入队操作***************/
int InQueue(CircleQueue *q, BTree t)
{
if((q->rear + 1) % MAXSIZE == q->front)
{
printf("The Queue is Full\n");
return -1;
}
else
{
q->rear = (q->rear + 1) % MAXSIZE;
q->p[q->rear] = t;
q->num++;
}
return 1;
}
BTree OutQueue(CircleQueue *q, BTree *t)
{
if(q->num == 0)
{
printf("The Queue is already empty!\n");
exit(0);
}
else
{
q->front = (q->front + 1) % MAXSIZE;
*t = q->p[q->front];
printf("%c" , t->data);
q->num--;
}
return *t;
}
/***********************************二叉树部分************************************8************/
/***********创建二叉树*****************/
BTree *CreateBTree()
{
BTree *T; //T是指向结构体元素的指针
char ch;
scanf("%ch", &ch); //输入节点数据
if(ch == '#')
{
T = NULL; //返回空指针
}
else
{
T = malloc(sizeof(BTree)); //开辟存储空间
T->data = ch; //保存数据元素
T->lchild = CreateBTree(); //先序建立左子树
T->rchild = CreateBTree(); //先序建立右子树
}
return T;
}
/**********先序遍历二叉树************/
void PreOrderTraverse(BTree *T) //先序遍历函数
{
if(T)
{
printf("%c", T->data); //输出当前结点数据
PreOrderTraverse(T->lchild); //先序遍历左子树
PreOrderTraverse(T->rchild); //先序遍历右子树
}
}
/***********层次遍历二叉树***********/
void Printbylevel(BTree *T)
{
BTree *tmp = T;
CircleQueue *q ;
q = InitQueue();
if(T == NULL)
{
printf("根节点为空") ; //根节点为空，返回-1
}
else
{
InQueue(q, *tmp); //根节点(非指针)入队
}
while(q->num) //队列不为空
{
OutQueue(q,tmp); //指针出队//输出出队元素
if(tmp->lchild) //左子树不为空
{
InQueue(q, *tmp->lchild);//左子树入队
}
if(tmp->rchild) //右子树不为空
{
InQueue(q, *tmp->rchild);//右子树入队
}
}
}
int main()
{
BTree *t;
t = CreateBTree();
printf("The pre order is : ");
PreOrderTraverse(t);
printf("\nThe Level Order is : ");
Printbylevel(t);
return 0;
}
代码的注释也比较详细，适合各位朋友互相参考，欢迎留言交流！！