本文是数据结构基础系列(6)：树和2叉树中第12课时层次遍历算法的例程。

【2叉树的层次遍历算法】
　　实现2叉树的层次遍历算法，并对用”A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”创建的2叉树进行测试。
　　请利用2叉树算法库。

［参考解答］（btreee.h见算法库）

#include #include "btree.h" void LevelOrder(BTNode *b) { BTNode *p; BTNode *qu[MaxSize]; //定义环形队列,寄存节点指针 int front,rear; //定义队头和队尾指针 front=rear=-1; //置队列为空队列 rear++; qu[rear]=b; //根节点指针进入队列 while (front!=rear) //队列不为空 { front=(front+1)%MaxSize; p=qu[front]; //队头出队列 printf("%c ",p->data); //访问节点 if (p->lchild!=NULL) //有左孩子时将其进队 { rear=(rear+1)%MaxSize; qu[rear]=p->lchild; } if (p->rchild!=NULL) //有右孩子时将其进队 { rear=(rear+1)%MaxSize; qu[rear]=p->rchild; } } } int main() { BTNode *b; CreateBTNode(b,"A(B(D,I)))"); printf("2叉树b: "); DispBTNode(b); printf(" "); printf("层次遍历序列: "); LevelOrder(b); DestroyBTNode(b); return 0; }

注：在main函数中，创建的用于测试的2叉树以下――