【说明】
一般的树结构常采用孩子-兄弟表示法表示，即用二叉链表作树的存储结构，链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如，图10-8(a)所示的树的孩子-兄弟表示如图10-8(b)所示。
函数LevelTraverse()的功能是对给定树进行层序遍历。例如，对图10-1所示的树进行层序遍历时，结点的访问次序为D B A E F P C。
对树进行层序遍历时使用了队列结构，实现队列基本操作的函数原型如下表所示：
| 函数原型 | 说 明 |
| Void InitQueue(Queue*Q) | 初始化队列 |
| Bool IsEmpty(Queue Q) | 判断队列是否为空，若是则返回TRUE，否则返回FALSE |
| Void EnQueue(Queue*Q,TreeNode p) | 元素入队列 |
| Void DeQueue(Queue*Q,TreeNode*p) | 元素出队列 |
Bool、Status类型定义如下：
typedef enum { FALSE=0，TRUE=1 } Bool；
typedef enum { OVERFLOW=-2，UNDERFLOW=-1，ERROR=0，OK=1}Status；
树的二叉链表结点定义如下：
typedef struct Node {
char data；
struct Node *firstchild，*nextbrother；
} Node，*TreeNode；
【函数】
Status LevelTraverse ( TreeNode root )
{ /*层序遍历树，树采用孩子-兄弟表示法，root是树根结点的指针*/
Queue tempQ；
TreeNode ptr，brotherptr；
if (! root)
return ERROR；
InitQueue(&tempQ)；
(1) ；
brotherptr = root -＞ nextbrother；
while (brotherptr) {
EnQueue(&tempQ，brotherptr)；
(2) ；
}/*end-while*/
while( (3) ){
(4) ；
printf("%c＼t"，ptr-＞data)；
if( (5) )continue；
(6) ；
brotherptr = ptr-＞firstchild-＞nextbrother；
while (brotherptr) {
EnQueue(&tempQ，brotherptr)；
(7) ；
}/*end-while*/
}/*end-while*/
return OK；
}/*LevelTraverse*/
参考答案：
解析：(1)EnQueue(&tempQ，root) (2)brotherptr=brotherptr-＞nextbrother (3)!IsEmpty(tempQ)，或其等价形式 (4)DeQueue(&tempQ，&ptr) (5)!ptr-＞firstchild，或其等价形式 (6)EnQueue(&tempQ，ptr-＞firstchild) (7)brotherptr=brotherptr-＞nextbrother
[分析]： 本题考查树结构的存储及遍历运算。 借助队列结构对树进行层序遍历时，每个结点都进出队列一次，结点出队列时进行访问。其过程是：首先令树根结点入队，若是森林(树根之间互为兄弟)，接着则令其余树的根结点入队，然后在队列非空的情况下，队头结点出队，访问该结点同时令其孩子结点入队。以此类推，直到队列为空。 队列可以保证访问结点时按照层次和自左至右的顺序。 函数中，代码“InitQueue(&tempQ)； (1) ”初始化队列并令根结点入队列，因此空(1)处应填入“EnQueue(&tempQ，root)”。 采用二叉树存储树结构时，其右分支表示兄弟关系，因此队头结点出队时，应沿右分支将队头结点的所有孩子依次加入队列。以下代码处理第一棵树的兄弟结点，如下： while (brotherptr){ EnQueue(&tempQ，brotherptr)； (2) ； }/*end-while*/ 因此，空(2)处应填入“brotherptr=brotherptr -＞ nextbrother”。这样，就完成了第一层结点的处理。 显然，空(3)处应判断队列是否为空，即填入“!IsEmpty(tempQ)”。队列非空的情况下，令队头元素出队列，即空(4)处应填入“DeQueue(&tempQ，&ptr)”。这是使用队列或栈结构存储元素以实现某种运算的基本特点。 若一个结点不存在孩子，则其firstchild指针域为空，也无需令其孩子结点入队列。 因此，空(5)处应填入“!ptr-＞firstchild”。反之，若一个结点有孩子，则应首先令其第一个孩子结点入队列，然后通过右分支链使其他孩子结点入队列。因此，空(6)处应填入“EnQueue(&tempQ，ptr-＞firstchild)”，空(7)处应填入“brotherptr =brotherptr-＞nextbrother”。