摘要:试题五(15分)阅读以下说明、图和C代码,将应填入(n)处的字句写在答题纸的对应栏内。[说明]一般的树结构常采用孩子一兄弟表示法表示,即用二义链表作树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,图5-1(a)所示的树的孩子一兄弟表示如图5-1(b)所示。函数LevelTraverse()的功能是
试题五(15分)
阅读以下说明、图和C代码,将应填入 (n) 处的字句写在答题纸的对应栏内。
[说明]
一般的树结构常采用孩子一兄弟表示法表示,即用二义链表作树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,图5-1(a)所示的树的孩子一兄弟表示如图5-1(b)所示。
函数LevelTraverse ()的功能是对给定树进行层序遍历。例如,对图5-1所示的树进行层序遍历时,结点的访问次序为:D B A E F P C。
对树进行层序遍历时使用了队列结构,实现队列基本操作的函数原型如下表所示:
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 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*/
[答案讨论]
软考备考资料免费领取
去领取