2. 计算机
  3. 阅读下列C函数和函数说明，将应填入(n)处的字句写在对应栏内。 【说明】 函数DeleteNode (Bitree *r, int e)的功能是：在树根结点指针为r的二叉查找(排序)树上删除键值为e的结点，若删除成功，则函数返回0，否则函数返

阅读下列C函数和函数说明，将应填入(n)处的字句写在对应栏内。 【说明】 函数DeleteNode (Bitree *r, int e)的功能是：在树根结点指针为r的二叉查找(排序)树上删除键值为e的结点，若删除成功，则函数返回0，否则函数返

admin2010-01-15  84
问题 阅读下列C函数和函数说明，将应填入(n)处的字句写在对应栏内。
    【说明】
   函数DeleteNode (Bitree *r, int e)的功能是：在树根结点指针为r的二叉查找(排序)树上删除键值为e的结点，若删除成功，则函数返回0，否则函数返回-1。二叉查找树结点的类型定义为：
   typedef struct Tnode{
       int data；    /*结点的键值*/
       struct Tnode *Lchild, *Rchild；    /*指向左、右子树的指针*/
   }*Bitree：
   在二叉查找树上删除一个结点时，要考虑3种情况：
   ①若待删除的结点p是叶子结点，则直接删除该结点；
   ②若待删除的结点p只有一个子结点，则将这个子结点与待删除结点的父结点直接连接，然后删除结点p；
   ③若待删除的结点p有两个子结点，则在其左子树上，用中序遍历寻找关键值最大的结点s，用结点s的值代替结点p的值，然后删除结点s，结点s必属于上述①、②情况之一。
   【函数】
   int DeleteNode (Bitree *r，int e)    {
       Bitree p=*r,pp，s，c；
       while  ( (1) ){  /*从树根结点出发查找键值为e的结点*/
          pp=p;
          if(e＜p-＞data)  p=p-＞Lchild；
          else p=p-＞Rchild；
       }
       if(!P)  return-1；    /*查找失败*/
       if(p-＞Lchild && p-＞Rchild)  {/*处理情况③*/
          s=(2)；pp=p
          while  (3)   {pp=s；s=s-＞Rchild;}
          p-＞data=s-＞data；    p=s；
       }
       /*处理情况①、②*/
       if ( (4) )  c=p-＞Lchild；
       else c=p-＞Rchild；
       if(p==*r)  *r=c；
       else if (  (5)  ) pp-＞Lchild=c；
          else pp-＞Rchild=c；
       free (p)；
       return 0；
   }
选项
答案(1)p &&p-＞data!=e；或p!=NULL&&p-＞data!=e或p&&(*p).data!=e (2)p-＞Lchild或(*p).Lchild (3)p-＞Rchild或(*p).Rchild (4)p-＞Lchild或(*p).Lchild (5)pp-＞Lchid＝p或p＝(*pp).child
解析 本程序的功能是删除二叉查找树的一个结点。题目中对怎样删除结点有着比较详细的说明。
   第1种情况就是删除叶子结点，叶子结点可以直接删除，这一点很好理解，因为叶子结点删除后并不会打乱查找树的顺序。
   第2种情况是删除只有一个子结点的结点，只需把其子结点代替父结点即可。若子结点下有子树，子树结构不变。
   第3种情况要复杂一点，要用到二叉查找树的一些性质，就是结点右子树的所有结点都大于根结点，左子树所有结点都小于根结点。所以，当删除了有左右子树的结点时，要在左子树找最大的结点，来替换被删结点。
转载请注明原文地址:https://kaotiyun.com/show/w0DZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

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

软考中级

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