2. 计算机
  3. 一般的树结构常采用孩子-兄弟表示法表示，即用二叉链表作为树的存储结构，链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如，如图15-1(a)所示的树的孩子-兄弟表示如图15-1(b)所示。 。 函数LevelTraverse(

一般的树结构常采用孩子-兄弟表示法表示，即用二叉链表作为树的存储结构，链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如，如图15-1(a)所示的树的孩子-兄弟表示如图15-1(b)所示。 。 函数LevelTraverse(

admin2015-06-03  91
问题 一般的树结构常采用孩子-兄弟表示法表示，即用二叉链表作为树的存储结构，链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如，如图15-1(a)所示的树的孩子-兄弟表示如图15-1(b)所示。
。
    函数LevelTraverse()的功能是对给定树进行层序遍历。例如，当对图15-1(a)中的树进行层序遍历时，结点的访问次序为DBAEFPC。
对树进行层序遍历时使用了队列结构，实现队列基本操作的函数原型如表15-1所示。
。
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 *firstchiid，*nextbrother；
}Node，*TreeNode；
【函数代码】
Status LevelTraverse(TreeNode root)
{／*层序遍历树，树采用孩子一兄弟表示法，root是树根结点的指针*／
    Queue temQ；
    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。
解析 解答此题的关键在于理解用队列层序遍历树的过程。算法的流程是这样的：首先将树根结点入队，然后将其所有兄弟结点入队(当然，由于是根结点，故无兄弟结点)；完成这一操作以后，便开始出队、打印；在打印完了之后，需要进行一个判断，判断当前结点有无孩子结点，若有孩子结点，则将孩子结点入队，同时将孩子结点的所有兄弟结点入队；完了以后继续进行出队操作；出队后再次判断当前结点是否有孩子结点，并重复上述过程，直至所有结点输出。
    这一描述可能过于理论，难以理解，接下来以本题为例来说明此过程。首先将树根结点D入队，并同时检查是否有兄弟结点，对于兄弟结点应一并入队。这里的D没有兄弟结点，所以队列此时应是：
    D
    接下来执行出队操作。D出队，出队以后检查D是否有子结点，经检查，D有子结点B，所以将B入队，同时将B的兄弟结点：A和E按顺序入队。得到队列：
    B
    A
    E
    接下来再执行出队操作。B出队，同时检查B是否有子结点，B无子结点，所以继续执行出队操作。A出队，同时检查A是否有子结点，A有子结点F，所以将F入队，同时将F的兄弟结点P入队。得到队列：
    E
    F
    P
    接下来再次执行出队操作。E出队，E有子结点C，所以C入队。得：
    F
    P
    C
    接下来再次执行出队操作。F出队，F无子结点，继续出队操作，P出队，仍无子结点，最后C出队，整个过程结束。
    通过对算法的详细分析，现在便可轻松得到答案。(1)应是对根结点root执行入队操作，即EnQueue(&tempQ，root)。(2)在一个循环当中，循环变量是brotherptr，此变量无语句对其进行更新，所以(2)必定是更新brotherptr。结合前面的算法分析可知(2)应填：brotherptr=brotherptr->nextbrother。(3)、(4)加上后面的语句“printf(“％c＼t”， ptr->data)；”是控制数据的输出，这些数据应是从队列中得到，所以此处必有出队操作，同时在出队之前应判断队列是否为空，所以(3)、(4)填：!IsEmpty(tempQ)和DeQueue(&tempQ，&ptr)。(5)实际上是问“在什么情况下，要持续进行出队操作?”，前面的算法分析中已指出：若出队结点无子结点，则继续进行出队操作，所以(5)填!ptr->firstchild。(6)和(7)所在的语句段的功能是将刚出队结点的子结点及其兄弟结点入队，所以(6)填：EnQueue(&tempQ，ptr->firstchild)。(7)和(2)相同，填brotherptr=brotherptr->nextbrother。
转载请注明原文地址:https://www.kaotiyun.com/show/FdDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

相关试题推荐
随机试题
最新回复(0)