【说明】
一般的树结构常采用孩子一兄弟表示法表示，即用二叉链表代表树的存储结构，链表中节点的两个链域分别指向该节点的第一个孩子节点和下一个兄弟节点，例如，如图5-9(a)所示的树和如图5-9(b)所示的树的孩子一兄弟表示。
函数LevelTraverse()的功能是对给定树进行层序遍历。例如，对如图5-9所示的树进行层序遍历时，节点的访问次序为DBAEFPC。
对树进行层序遍历时使用了队列结构，实现队列基本操作的函数原型如表5-12所示。
表5-12 实现队列基本操作的函数原型表
| 函 数 原 型 | 说 明 |
| void InitQueue(Queue *Q) | 初始化队列 |
| Bool IsEmpty(Queue *Q) | 判断队列是否为空，若是则返回true，否则返回alse |
| void EnQueue(Queue *Q, TreeNode p) | 元素入队列 |
| void DeQueue(Queue *Q, TreeNode *p) | 元素出队列 |
typedef enum{FALSE=0, TRUE=1}Bool;
typedef enum{OVERFLOW=-2, UNDERFLOW=-1, ERROR=0, OK=1)Status;
树的二叉链表节点定义如下：
typedef struct N6de{
char data;
struct Node *firstchild, *nextbrother;
}Node, *TreeNode;
【C函数程序】
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-＞firstchiid-＞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[要点解析] 这是一道要求读者掌握树结构的存储及遍历运算的程序分析题。本试题的解答思路如下。 队列可以保证访问节点时按照层次和自左至右的顺序。借助队列结构对树进行层序遍历时，每个节点都进出队列一次，节点出队列时进行访问。其过程是，首先令树根节点入队，若是森林(树根之间互为兄弟)，接着则令其余树的根节点入队，然后在队列非空的情况下，队头节点出队，访问该节点同时令其孩子节点入队。依此类推，直到队列为空。 在试题所给出的【C函数程序】中，代码“InitQueue(&tempQ)； (1) ；”完成初始化队列并令根节点入队列的功能，因此(1)空缺处所填写的内容是“EnQueue(&tempQ，root)”。 采用二叉树存储树结构时，其右分支表示兄弟关系，因此队头节点出队时，应沿右分支将队头节点的所有孩子依次加入队列。(2)空缺处所在的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”。