按层次遍历二叉树，用队列作为缓冲

//设立一个队列Q，用于存放结点，以保证二叉树结点按照层次顺序从左到右进入队列。若二叉树bt非空，首先，
//将根结点插入队列，然后，从队列中删除一个结点，访问该结点，并将该结点的孩子结点（如果有的话）插入
//队列。
#include <stdio.h>
#include <stdlib.h>

//定义二叉树的结点
typedef struct btnode
{
　　char data;
　　struct btnode *lchild,*rchild;
}bitree,*Bitree;

//定义链接队列的结点
typedef struct LinkQueueNode
{
　　bitree *data;
　　struct LinkQueueNode *next;
}LKQueNode;

//定义队列，队列有头指针和尾指针
typedef struct LKQueue
{
　　LinkQueueNode *front,*rear;
}LKQue;

//初始化队列
void InitQueue(LKQue * LQ)
{
　　LKQueNode *p;
　　p=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));
　　LQ->front=p;
　　LQ->rear=p;
　　LQ->front->next=NULL;
}

//判断队列是否为空队列
int EmptyQueue(LKQue *LQ)
{
　　if(LQ->front==LQ->rear)
　　　　return 1;
　　else
　　　　return 0;
}
//入队操作
void EnQueue(LKQue *LQ,Bitree x)
{
　　LKQueNode *p;
　　p=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));
　　p->data=x;
　　p->next=NULL;
　　LQ->rear->next=p;
　　LQ->rear=p;
}
//出队操作
int OutQueue(LKQue *LQ)
{

　　LKQueNode *s;
　　if(EmptyQueue(LQ))
　　{
　　　　exit(0);
　　　　return 0;
　　}
　　else
　　{
　　　　s=(LQ->front)->next;
　　　　(LQ->front)->next=s->next;
　　　　if(s->next==NULL)
　　　　　　LQ->rear=LQ->front;
　　　　free(s);
　　return 1;
　　}
}

//取队列首元素
Bitree GetHead(LKQue *LQ)
{
　　LKQueNode *p;
　　bitree *q;
　　if(EmptyQueue(LQ))
　　　　return q;
　　else
　　{
　　　　p=(LQ->front)->next;
　　　　return p->data;
　　}
}

//创建二叉树
Bitree CreateBinTree()
{
　　char ch;
　　Bitree t;
　　ch=getchar();
　　if(ch=='#')
　　{
　　　　t=NULL;
　　}
　　else
　　{
　　　　t=(Bitree)malloc(sizeof(bitree));
　　　　t->data=ch;
　　　　t->lchild=CreateBinTree();
　　　　t->rchild=CreateBinTree();
　　}
return t;
}

//访问结点
void visit(Bitree pp)
{
　　printf("%c ",pp->data);
}

//按层遍历二叉树
void LevelOrder(Bitree T)
{
　　LKQue Q;
　　Bitree p;
　　InitQueue(&Q);
　　if(T!=NULL)
　　{
　　　　EnQueue(&Q,T);
　　　　while(!EmptyQueue(&Q))
　　　　{
　　　　　　p=GetHead(&Q);
　　　　　　OutQueue(&Q);
　　　　　　visit(p);
　　　　　　if(p->lchild!=NULL)
　　　　　　　　EnQueue(&Q,p->lchild);
　　　　　　if(p->rchild!=NULL)
　　　　　　　　EnQueue(&Q,p->rchild);
　　　　}
　　}
}

//主函数
void main()
{
　　Bitree TT;
　　printf("按层次遍历二叉树，借助队列作为缓冲，空指针用‘#’表示。\n");
　　printf("例如：ABD#E##F##C#GH### \n");
　　TT=CreateBinTree();
　　printf("层次遍历序列为：\n");
　　LevelOrder(TT);
　　printf("\n");
　　system("pause");
}