刷题刷出新高度,偷偷领先!偷偷领先!偷偷领先! 关注我们,悄悄成为最优秀的自己!

简答题

阅读以下说明和C函数,填补代码中的空缺,将解答填入答题纸的对应栏内。
[说明]
二叉树的宽度定义为含有结点数最多的那一层上的结点数。函数GetWidth()用于求二叉树的宽度。其思路是根据树的高度设置一个数组counter[],counterl[i]存放第i层上的结点数,并按照层次顺序来遍历二叉树中的结点,在此过程中可获得每个结点的层次值,最后从counter[]中取出最大的元素就是树的宽度。
按照层次顺序遍历二叉树的实现方法是借助一个队列,按访问结点的先后顺序来记录结点,离根结点越近的结点越先进入队列,具体处理过程为:先令根结点及其层次号(为1)进入初始为空的队列,然后在队列非空的情况下,取出队头所指示的结点及其层次号,然后将该结点的左子树根结点及层次号入队列(若左子树存在),其次将该结点的右子树根结点及层次号入队列(若右子树存在),然后再取队头,重复该过程直至完成遍历。
设二叉树采用二叉链表存储,结点类型定义如下:

typedef struct BTNode { 

    TElemType data; 

    struct BTNode
*left,*right;
队列元素的类型定义如下:
typedef  struct { 

    BTNode *ptr; 

    int LevelNumber; 

    )QElemType;
GetWidth()函数中用到的函数原型如下所述,队列的类型名为QUEUE:
[C函数] 

    int
GetWidth(BiTree root) 

    { 

    QUEUE  Q; 

    QElemType a,
 b; 

    int
width,height=GetHeight(root); 

    int
i,*counter=(int*)calloc(height+1,sizeof(int)); 

    if (______)  
 return-1;    /*申请空间失败*/ 

    if(!root)  
 return 0;    /*空树的宽度为0*/ 

    if(______)  
 return-1;    /*初始化队列失败时返回*/ 

    a.ptr=root;  
 a.LeveiNumber=1; 

  
 if(!EnQueue(&Q,a))return-1;    /*元素入队列操作失败时返回*/ 

  
 while(!isEmpty(Q)){ 

  
 if(______)return-1;    /*出队列操作失败时返回*/ 

  
 counter[b.LevelNumber]++;  /*对层号为b.LevelNumber的结点计数*/ 

    if(b.ptr->left)  { /*若左孔树存在,则左孔树根结点及其层次号入队*/ 

    a.ptr=b.ptr->left; 

    a.LevelNumber=
______; 

    if (
!EnQueue(&Q,a))return-1; 

    } 

    if (bptr->right) {/*若右孔树存在,则右孔树根结点及其层次号入队*/ 

    a.ptr=b.ptr->right; 

  
 a.LevelNumber=______; 

  
 if(!EnQueue(&Q,a))return-1; 

    } 

    } 

    width=counter[1]; 

    for(i=1;i<height+1;i++)    /*求counter[]中的最大值*/ 

    if(______)
width=counter[i]; 

    free(counter); 

    return width; 

    }

使用微信搜索喵呜刷题,轻松应对考试!

答案:

!counter 或0==counter 或NULL==counte r或等价表示
!InitQueue(&Q)  或0==InitQueue(&Q) 或等价表示
!DeQueue(&Q,&b)或0==DeQueue(&Q,&b)  或等价表示
b.LevelNumber+1    或等价表示
b.LevelNumber+1    或等价表示
counter[i]>width    或等价表示

解析:

本题考查了二叉树的宽度计算以及C语言的基本应用。首先,我们需要仔细阅读题目中的说明,了解函数处理逻辑并完成代码。对于每个空,我们可以根据题目的描述和函数的逻辑进行填充。对于空(1),我们需要检查内存分配是否成功,如果失败则返回-1,因此应填入表示错误的条件,如"!counter"或NULL == counter等。对于空(2),我们需要初始化队列,如果初始化失败则返回-1,因此应填入队列初始化失败的条件,如"!InitQueue(&Q)“等。对于空(3),我们需要进行出队列操作,如果操作失败则返回-1,因此应填入出队列操作失败的条件,如”!DeQueue(&Q, &b)“等。对于空(4)和空(5),我们需要计算子结点的层次号,根据二叉树的性质,子结点的层次号应该比父结点大1,因此应填入"b.LevelNumber + 1”。最后,对于空(6),我们需要找到counter数组中的最大值,即树的宽度,因此应填入表示当前元素大于当前最大宽度的条件,如"counter[i] > width"。

创作类型:
原创

本文链接:阅读以下说明和C函数,填补代码中的空缺,将解答填入答题纸的对应栏内。[说明]二叉树的宽度定义为含有结

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速,微信扫码,获取考试解析、体验刷题服务,开启你的学习加速器!

分享考题
share