#include
#include
struct Nodep /*树结点类型*/
{
char data;
struct Nodep * lired; //左孩子
struct Nodep * rired; //右孩子
};
struct Queue //队列结点
{
Nodep * ch;
struct Queue * next;
};
struct BQueue //队列指针
{
Queue * rear; //队尾指针
Queue * front; //对头指针
};
void input(BQueue * Head) /*初始化队列*/
{
Head->front=Head->rear=(Queue*)malloc(sizeof(Queue));
Head->front->next=NULL;
}
void output(BQueue * Head,Nodep * root) //入队列
{
Queue * s;
s=(Queue*)malloc(sizeof(Queue));
s->ch=root;
s->next=NULL;
Head->rear->next=s;
Head->rear=s;
printf("入队列成功");
}
void Queuebtr(BQueue * Head, Nodep * root) //出队列
{
char ch; //用于存放出队列的元素
Queue * s; //临时变量;
root=s->ch;
s=Head->front->next;
ch=root->data;
Head->front->next=s->next;
if(Head->front==Head->rear)
Head->rear=Head->front;
free(s);
printf("%c",ch);
}
Nodep * gouzao()
{
char ch;
Nodep * root;
scanf("%c",&ch);
if(ch=='0')
root=NULL;
else
{
root=(Nodep *)malloc(sizeof(Nodep));
root->data=ch;
root->lired=gouzao();
root->rired=gouzao();
}
return root;
}
void cengxu(Nodep * root)
{
BQueue * head;
Nodep * roots;
input(head); //初始化队列
roots=root;
output(head,roots); //进队列和根节点
while(head->front!=NULL)
{
Queuebtr(head,roots); //出根节点
if(roots->lired!=NULL)
{
output(head,root->lired); //进左
}
if(roots->rired!=NULL)
{
output(head,root->rired); //进右
}
}
printf("\n");
}
void main()
{
Nodep * root;
root=gouzao();
cengxu(root);
}