层序遍历二叉树

#includestdio.h#includestdlib.h#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-1#defineMAXQSIZE10typedefintStatus;/*Status是函数的类型,其值是函数结果状态代码，如OK等*/typedefcharTElemType;/*二叉树的元素类型为字符型*/typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;/*左右孩子指针*/}BiTNode,*BiTree;typedefBiTreeQElemType;/*设栈元素为二叉树的指针类型*/typedefstruct{QElemType*base;intfront;/*头指针,若队列不空,指向队列头元素*/intrear;/*尾指针,若队列不空,指向队列尾元素的下一个位置*/}SqQueue;StatusInitQueue(SqQueue*Q){/*构造一个空队列Q*/(*Q).base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));if(!(*Q).base)/*存储分配失败*/exit(OVERFLOW);(*Q).front=(*Q).rear=0;returnOK;}StatusQueueEmpty(SqQueueQ){/*若队列Q为空队列,则返回TRUE,否则返回FALSE*/if(Q.front==Q.rear)/*队列空的标志*/returnTRUE;elsereturnFALSE;}StatusEnQueue(SqQueue*Q,QElemTypee){/*插入元素e为Q的新的队尾元素*/if(((*Q).rear+1)%MAXQSIZE==(*Q).front)/*队列满*/returnERROR;(*Q).base[(*Q).rear]=e;(*Q).rear=((*Q).rear+1)%MAXQSIZE;returnOK;}StatusDeQueue(SqQueue*Q,QElemType*e){/*若队列不空,则删除Q的队头元素,用e返回其值,并返回OK;否则返回ERROR*/if((*Q).front==(*Q).rear)/*队列空*/returnERROR;*e=(*Q).base[(*Q).front];(*Q).front=((*Q).front+1)%MAXQSIZE;returnOK;}voidCreateBiTree(BiTree*T){/*按先序次序输入二叉树中结点的值,构造二叉链表表示的二叉树T。*/TElemTypech;scanf(%c,&ch);if(ch=='')*T=NULL;else{*T=(BiTree)malloc(sizeof(BiTNode));if(!*T)exit(OVERFLOW);(*T)-data=ch;/*生成根结点*/CreateBiTree(&(*T)-lchild);/*构造左子树*/CreateBiTree(&(*T)-rchild);/*构造右子树*/}}StatusvisitT(TElemTypee){printf(%c,e);returnOK;}voidLevelOrderTraverse(BiTreeT,Status(*Visit)(TElemType)){/*采用二叉链表存储结构，Visit是对数据元素操作的应用函数。*//*层序遍历二叉树T算法(利用队列)，对每个数据元素调用函数Visit*/SqQueueQ;BiTreeP;InitQueue(&Q);//初始化队列if(T)EnQueue(&Q,T);while(Q.front!=Q.rear){DeQueue(&Q,&P);Visit(P-data);if(P-lchild)EnQueue(&Q,P-lchild);//若存在左孩子，左孩子进队列if(P-rchild)EnQueue(&Q,P-rchild);//若存在右孩子，右孩子进队列}return;}main(){BiTreeT;printf(请先序输入二叉树\n);CreateBiTree(&T);printf(\n层序遍历二叉树:\n);LevelOrderTraverse(T,visitT);return0;}