#define CHAR /* */
#include <stdio.h> /* EOF(=^Z F6),NULL */
#include <stdlib.h>
#include<math.h> /* floor(),ceil(),abs() */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status; /* Status , , OK */
#ifdef CHAR
typedef char TElemType;
TElemType Nil=' '; /* */
#endif
#ifdef INT
typedef int TElemType;
TElemType Nil=0; /* 0 */
#endif
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild; /* */
}BiTNode,*BiTree;
typedef BiTree QElemType; /* */
typedef struct QNode//
{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct //
{
QueuePtr front,rear; /* 、 */
}LinkQueue;
Status InitBiTree(BiTree *T)
{ /* : T */
*T=NULL;
return OK;
}
void CreateBiTree(BiTree *T)
{
TElemType ch;
#ifdef CHAR
scanf("%c",&ch);
#endif
#ifdef INT
scanf("%d",&ch);
#endif
if(ch==Nil) /* */
*T=NULL;
else
{
*T=(BiTree)malloc(sizeof(BiTNode));
if(!*T)
exit(OVERFLOW);
(*T)->data=ch; /* */
CreateBiTree(&(*T)->lchild); /* */
CreateBiTree(&(*T)->rchild); /* */
}
}
Status InitQueue(LinkQueue *Q)
{ /* Q */
(*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode));
if(!(*Q).front)
exit(OVERFLOW);
(*Q).front->next=NULL;
return OK;
}
Status QueueEmpty(LinkQueue Q)
{ /* Q , TRUE, FALSE */
if(Q.front==Q.rear)
return TRUE;
else
return FALSE;
}
Status EnQueue(LinkQueue *Q,QElemType e)
{ /* e Q */
QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
if(!p) /* */
exit(OVERFLOW);
p->data=e;
p->next=NULL;
(*Q).rear->next=p;
(*Q).rear=p;
return OK;
}
Status DeQueue(LinkQueue *Q,QElemType *e)
{ /* , Q , e , OK, ERROR */
QueuePtr p;
if((*Q).front==(*Q).rear)
return ERROR;
p=(*Q).front->next;
*e=p->data;
(*Q).front->next=p->next;
if((*Q).rear==p)
(*Q).rear=(*Q).front;
free(p);
return OK;
}
void LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType))
{ /* : T ,Visit */
/* : T( ), Visit */
LinkQueue q;
QElemType a;
if(T)
{
InitQueue(&q);
EnQueue(&q,T);
while(!QueueEmpty(q))
{
DeQueue(&q,&a);
Visit(a->data);
if(a->lchild!=NULL)
EnQueue(&q,a->lchild);
if(a->rchild!=NULL)
EnQueue(&q,a->rchild);
}
printf("
");
}
}
Status visitT(TElemType e)
{
#ifdef CHAR
printf("%c ",e);
#endif
#ifdef INT
printf("%d ",e);
#endif
return OK;
}
void main()
{
BiTree T;
InitBiTree(&T);
#ifdef CHAR
printf(" ( :ab a ,b )
");
#endif
#ifdef INT
printf(" ( :1 2 0 0 0 1 ,2 )
");
#endif
CreateBiTree(&T);
printf(" :
");
LevelOrderTraverse(T,visitT);
}