#include<malloc.h> #include<stdio.h> #include<stdlib.h> #include<math.h> #define ERROR 0 #define OK 1 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define OVERFLOW 0 ] #define int Status typedef char TElemType; typedef struct BiTNode{ TElemType date; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;

typedef struct QNode{ TElemType date; struct QNode *next; }QNode,*QueuePtr; typedef struct{ QueuePtr front; QueuePtr rear; }LinkQueue; Status InitQueue(LinkQueue &Q){ Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode)); if(!Q.front) exit (OVERFLOW); Q.front->next = NULL; return OK; }

Status EnQueue (LinkQueue &Q,TElemType e){ //插入元素 QueuePtr p; p = (QueuePtr)malloc(sizeof(QNode)); if(!p) exit (OVERFLOW); p->date = e;p->next = NULL; Q.rear->next=p; Q.rear = p; return OK; }

Status DeQueue (LinkQueue &Q,TElemType &e){ if(Q.front == Q.rear) return ERROR; QueuePtr p; p = Q.front->next; e = p->date; Q.front->next = p->next; if(Q.rear == p) Q.rear = Q.front; free(p); return OK; }

Status CreateBiTree(BiTree T)//按先序次序输入二叉树中结点的值，'#'代表空树 { char ch; ch=getchar(); if (ch=='#') T=NULL; /* #代表空指针*/ else { T=(BiTree)malloc(sizeof(BiTNode));//*申请结点 */ if(!T) exit(OVERFLOW); T->data=ch; /*生成根结点 */ CreateBiTree(T->lchild); /*构造左子树 */ CreateBiTree(T->rchild); /*构造右子树 */ } return OK;

} Status LevelOrderTraverse(BiTree T ){ EnQueue(Q , T) ; While ( ! QueueEmpty(Q) ) { DeQueue(Q , p) ; printf (p->data) ; //打印结点 if (T->lchild) EnQueue(Q , T->lchild ) ; if (T->rchild) EnQueue(Q , T->rchild ) ; } return OK; }

void main () { BiTree T; CreateBiTree(T); LevelOrderTraverse ( T ) ; }