2. 计算机
  3. 阅读以下说明和C语言函数，将应填入(n)处的字句写在答题纸的对应栏内。 【说明】 一棵非空二叉树中“最左下”结点定义为：若树根的左子树为空，则树根为“最左下”结点；否则，从树根的左子树根出发，沿结点的左 子树分支向下查找，直到某个结点不存在左子树时

阅读以下说明和C语言函数，将应填入(n)处的字句写在答题纸的对应栏内。 【说明】 一棵非空二叉树中“最左下”结点定义为：若树根的左子树为空，则树根为“最左下”结点；否则，从树根的左子树根出发，沿结点的左 子树分支向下查找，直到某个结点不存在左子树时

admin2008-01-03  77
问题 阅读以下说明和C语言函数，将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
   一棵非空二叉树中“最左下”结点定义为：若树根的左子树为空，则树根为“最左下”结点；否则，从树根的左子树根出发，沿结点的左

子树分支向下查找，直到某个结点不存在左子树时为止，该结点即为此二叉树的“最左下”结点。例如，下图所示的以 A为根的二叉树的“最
左下”结点为D，以C为根的子二叉树中的“最左下”结点为C。
   
   二叉树的结点类型定义如下：
   typedef stmct BSTNode{
     int data；
     struct BSTNode*lch,*rch；//结点的左、右子树指针
   }*BSTree；
   函数BSTree Find  Del(BSTree  root)的功能是：若root指向一棵二叉树的根结点，则找出该结点的右子树上的“最左下”结点*p，并从
树于删除以*p为根的子树，函数返回被删除子树的根结点指针；若该树根的右子树上不存在“最左下”结点，则返回空指针。
【函数】
   BSTrce Find_Del(BSTreeroot)
   {  BSTreep,pre；
      if ( !root )  return NULL；    /*root指向的二叉树为空树*/
       (1)；    /*令p指向根结点的右子树*/
      if ( !p )  return NULL；
        (2)；    /*设置pre的初值*/
      while(p-＞lch){    /*查找“最左下”结点*/
      pre=p；p=(3)；
      }
      if ((4)==root)    /*root的右子树根为“最左下”结点*/
      pre-＞rch=NULL；
      else
       (5)=NULL；    /*删除以“最左下”结点为根的子树*/
      reurn p；
   }
选项
答案(1)p=root-＞rch (2)pre=root (3)p-＞lch (4)pre (5)pre-＞lch
解析 根据题目中的说明，函数BSTree Find  Del (BSTree  root)的功能是：若root指向一棵二叉树的根结点，则找出该结点的右子树上的“最

左下”结点*p，并从树中删除以 *p为根的子树，函数返回被删除子树的根结点指针；若该树根的右子树上不存在“最左下”结点，则返回空指

针。而一棵非空二叉树中“最左下”结点定义为：若树根的左子树为空，则树根为“最左下”结点；否则，从树根的左子树根出发，沿结点的

左子树分支向下查找，直到某个结点不存在左子树时为止，该结点即为此二叉树的“最左下”结点。
   因此，给定一棵非空二叉树后，其右子树上的“最左下”结点要么为右子树根结点自己，要么为右子树根的左子树结点。
   当二叉树非空时，root指向的结点是存在的，因此，令p指向根结点的右子树表示为“p=root-＞rch"。在二叉树上删除结点的操作实质上

是重置其父结点的某个子树指针，因此查找被删除结点时，需要保存被删结点的父结点指针，pre起的就是这个作用。空 (2)处应填入

“p=root"，使得指针pre与p指向的结点始终保持父子关系。根据“最左下”结点的定义，空(3)处应填入“p-＞lch"。
   当root的右子树根为“最左下”结点时，pre指针的指向就不会被修改，因此，空 (4)处应填入“pre”。若“最左下”结点在root的右子

树的左子树上，则删除以p指向的“最左下”结点为根的子树就是将pre(*p的父结点)的左子树指针置空，因此，空 (5)填入“pre-＞Ich"。
转载请注明原文地址:https://kaotiyun.com/show/OzjZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

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