[说明] 二叉树的二叉链表存储结构描述如下：typedef struct BiTNode{ datatype data; struct BiTNode *lchild, * rchild; /*左右孩子指针*/}BiTNode,* BiTree; 对二叉树进行层次遍历时，可设置一个队列结构，遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从队首取出一个元素，执行下面两个操作： (1) 访问该元素所指结点； (2) 若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针顺序入队。 此过程不断进行，当队列为空时，二叉树的层次遍历结束。 下面的函数实现了这一遍历算法，其中Visit(datatype a)函数实现了对结点数据域的访问，数组queue[MAXNODE]用以实现队列的功能，变量front和rear分别表示当前队首元素和队尾元素在数组中的位置。[函数]void LevelOrder(BiTree bt) /*层次遍历二叉树bt*/{ BiTree Queue[MAXNODE]; int front,rear; if(bt= =NULL)return; front=-1; rear=0; queue[rear]= (1) ; while(front (2) ){(3) ;Visit(queue[front]-＞data); /*访问队首结点的数据域*/if(queue[front]—＞lchild!：NULL){ rear++; queue[rear]= (4) ;}if(queue[front]-＞rchild! =NULL){ rear++; queue[rear]= (5) ;} }}
参考答案：
解析：(1) bt (2) ! =rear (3) front+ + (4) queue [front]-＞lchild(5) queue[front]-＞rchild[考点分析] 考查用C语言实现二叉树的层次遍历。 (1)遍历开始时队列长度为1，其中只存放了根结点bt；(2)遍历过程是一个循环访问队列的过程，其终止条件是队列为空，即front等于rear；(3)遍历到某结点时，该结点应退出队列，因此队首元素的位置应该增1；(4)此处应将队首结点的左孩子结点放入队列，即插在队尾；(5)此处应将队首结点的右孩子结点放入队列，即插在队尾。