#include <stdio.h>
#include <stdlib.h>
typedef struct BiTNode{
char data;
struct BiTNode *lchild, *rchild;
} BiTNode;
typedef BiTNode * BiTree;
//创建二叉树
BiTree CreateBiTree(){
char ch;
BiTree T;
scanf("%c",&ch);
if(ch=='#')
T=NULL;
else
{ if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))
exit(1);
T->data=ch;
T->lchild=CreateBiTree();
T->rchild=CreateBiTree();
}
return T;
}
//创建队列
typedef struct QueueNode{
BiTree data;
struct QueueNode *next;
}QueueNode;
typedef struct{
QueueNode *front;
QueueNode *rear;
}LinkQueue;
//队列初始化
void InitQueue(LinkQueue Q){
QueueNode *p;
p=(QueueNode *)malloc(sizeof(QueueNode));
if(p){
Q.front =Q.rear =p;
Q.front ->next =NULL;
}
else{
exit(0);
}
}
//入队
void Push(LinkQueue Q,BiTree x){
QueueNode *p;
p=(QueueNode *)malloc(sizeof(QueueNode));
if(!p){
printf("申请失败!\n");exit(0);
}
else{
p->data =x;
p->next =NULL;
Q.rear->next =p;
Q.rear =p;
}
}
//出队
void Pop(LinkQueue Q){
QueueNode *p;
p=(QueueNode *)malloc(sizeof(QueueNode));
if(Q.front ==Q.rear ){
printf("队空,出队失败!\n");
}
else{
p=Q.front->next ;
Q.front ->next=p->next ;
if(Q.rear ==p){
Q.rear =Q.front ;
}
free(p);
}
}
char GetHead(LinkQueue Q){
if(Q.front ==Q.rear ){
return 0;
}
else{
return Q.front->next->data->data;
}
}
//使用队列层序遍历
void FloorOrder(BiTree tree){
LinkQueue Q;
InitQueue( Q);
Push( Q,tree);
while(!(Q.front ==Q.rear )){
printf("%c",GetHead(Q));
if(tree->lchild!=NULL){
Push( Q,tree->lchild);
}
if(tree->rchild!=NULL){
Push( Q,tree->rchild);
}
Pop(Q);
}
}
int main() {
BiTree root=CreateBiTree();
FloorOrder( root);
return 0;
}