问答题
[说明]
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;
函数LevelTraverse的代码如下：
StatUS LevelTraverse(TreeNode root)
{ /*层序遍历树，树采用孩子-兄弟表示法，root是树根节点的指针*/
Queue tempQ;
TreeNode ptr, brotherptr;
if (!root)
return ERROR;
InitQueue (&tempQ);
______;
brotherptr = root→nextbrother;
while (brotherptr)
{
EnQueue (&tempQ, brotherptr);
______;
} /*end-while*/
while ______
{
______;
printf ("%c\t", ptr→data);
if (______)continue;
______;
brotherptr = ptr→firstchild→nextbrother;
while (brotherptr)
{
EnQueue (&tempQ, brotherptr);
______;
} /*end-while*/
} /*end-while*/
return OK;
} /*LevelTraverse*/
[说明]
一般的树型结构常采用孩子-兄弟表示法表示，即用二叉链表作树的存储结构，链表中节点的两个链域分别指向该节点的第一个孩子节点和下一个兄弟节点。例如，下图(a)中所示的树的孩子-兄弟表示如下图(b)中所示。
函数LeVelTraVerse()的功能是对给定树进行层序遍历。例如，对图中所示的树进行层序遍历时，节点的访问次序为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(Oueue *Q, TreeNode *p) | 元素出队列 |
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;
函数LevelTraverse的代码如下：
StatUS LevelTraverse(TreeNode root)
{ /*层序遍历树，树采用孩子-兄弟表示法，root是树根节点的指针*/
Queue tempQ;
TreeNode ptr, brotherptr;
if (!root)
return ERROR;
InitQueue (&tempQ);
______;
brotherptr = root→nextbrother;
while (brotherptr)
{
EnQueue (&tempQ, brotherptr);
______;
} /*end-while*/
while ______
{
______;
printf ("%c\t", ptr→data);
if (______)continue;
______;
brotherptr = ptr→firstchild→nextbrother;
while (brotherptr)
{
EnQueue (&tempQ, brotherptr);
______;
} /*end-while*/
} /*end-while*/
return OK;
} /*LevelTraverse*/