二叉树-层序遍历

#include<iostream>
#include<malloc.h>
#include<stdio.h>
#define  MAXSIZE  20  //最多结点个数
using namespace std;

/*二叉链表*/
typedef struct bnode{
char data;
struct bnode *lchild,*rchild;
}Bnode,* BTree;

/*循环队列*/
typedef BTree DataType;
typedef struct{
DataType data[MAXSIZE];
int front,rear;    
}SeqQueue,* PSeqQueue;

PSeqQueue Init_SeqQueue(void);//循环队列初始化
int Empty_SeqQueue(PSeqQueue Q);//判断队空
void In_SeqQueue(PSeqQueue Q,DataType x);//入队
void Out_SeqQueue(PSeqQueue Q,DataType * y);//出队
void Destory_SeqQueue(PSeqQueue * Q);//销毁队列

BTree CreateBinTree(void);//先序创建二叉树
void LevelOrder(BTree t);//层序遍历

/*主函数*/
int main(){
cout<<"\n请按先序次序输入各结点的值，以#表示空树(输入时可连续输入):\n";
BTree T=CreateBinTree();
if(!T){
cout<<"\n未建立树，请先建树！";
return 0;
}
cout<<"\n\n层序遍历:";
LevelOrder(T);

return 1;
}

/*循环队列初始化*/
PSeqQueue Init_SeqQueue(void){
PSeqQueue Q;
Q=(PSeqQueue)malloc(sizeof(SeqQueue));
if(Q){
Q->front=0;
Q->rear=0;
}
return Q;
}
/*判断队空*/
int Empty_SeqQueue(PSeqQueue Q){
if(Q && Q->front==Q->rear)
return 1;
else 
return 0;
}
/*入队*/
void In_SeqQueue(PSeqQueue Q,DataType x){
if(Q->front == (Q->rear+1)%MAXSIZE){
cout<<"队满不能入队！";
return;
}else{
Q->rear=(Q->rear+1)%MAXSIZE;
Q->data[Q->rear]=x;
}
}
/*出队*/
void Out_SeqQueue(PSeqQueue Q,DataType * y){
if(Empty_SeqQueue(Q)){
cout<<"队空不能出队！";
return;
}else{
Q->front=(Q->front+1)%MAXSIZE;
* y=Q->data[Q->front];
}
}
/*销毁队列*/
void Destory_SeqQueue(PSeqQueue * Q){
if(* Q)
free(* Q);
* Q=NULL;
}


/*先序创建二叉树*/
BTree CreateBinTree(void){
BTree t;
char ch=getchar();
if(ch=='#')
t=NULL;//读入#时，将相应节点指针置空
else{
t=(Bnode *)malloc(sizeof(Bnode));
t->data=ch;
t->lchild=CreateBinTree();//构造二叉树的左子树
t->rchild=CreateBinTree();//构造二叉树的右子树
}
return t;
}

/******************************层序遍历******************************/
void LevelOrder(BTree t){
BTree p;
PSeqQueue Q=Init_SeqQueue();
if(t)
In_SeqQueue(Q,t);

while(!Empty_SeqQueue(Q)){
Out_SeqQueue(Q,&p);
cout<<p->data<<" ";
if(p->lchild)
In_SeqQueue(Q,p->lchild);
if(p->rchild)
In_SeqQueue(Q,p->rchild);
}
Destory_SeqQueue(&Q);
}