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

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

admin2009-02-15  66
问题 阅读下列函数说明和C函数，将应填入(n)处。
    【函数3说明】
   函数DeleteNode(Bitree * r，int e)的功能是：在树根结点指针为r的二叉查找(排序)树上删除键值为e的结点，若删除成功，则函数返回0，否则函数返回-1。二叉查找树结点的类型定义为：
   typedef struct Tnode{
   int data；    /*结点的键值*/
   struct Tnode * Lchild，*Rchild；      /*指向左、右子树的指针*/
   } * Bitree；
   在二叉查找树上删除一个结点时，要考虑三种情况：
   ①若待删除的结点p是叶子结点，则直接删除该结点；
   ②若待删除的结点p只有一个子结点，则将这个子结点与待删除结点的父结点直接连接，然后删除结点P；
   ③若待删除的结点p有两个子结点，则在其左子树上，用中序遍历寻找关键值最大的结点s，用结点s的值代替结点p的值，然后删除结点s，结点s必属于上述①、②情况之一。
   【函数3】
   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&&(*p).data!=e(2)p -＞Lchild或(*p).Lchild (3)s-＞Rchild或(*s).Rchild(4)p-＞Lchild或 (*p).Lchild(5)p==pp-＞Lchild或p(*pp).Lchild
解析 (1)程序的第一条语句是变量的声明及赋初值，p指向二叉查找树的根。接下来从while循环的注释部分可以看出，该循环的功能是查找键值为e的结点。当循环的判断条件e＜p-＞data时，进入左子树查找，否则到右子树查找。程序中没有关于找到结点的处理代码，即循环内部只处理了没找到结点的情况，所以循环条件应该是当找到键值为e的结点时退出循环。另外，应注意一个隐含的限制条件“p’ NULL”时，表示已经查找完毕，无需进入循环。通过分析，(1)应填p &&p-＞data!=e。(2)if程序段是处理第三种情况的，由循环中的语句“s=s-＞Rchild；”可看出，s用于要删结点的左子树中查找键值最大的结点，所以s的初值应是要删除结点的左子结点。可见，(2)应填写 p-＞Lchild。(3)根据前面所述的二叉树规则可知，要找的结点s应是左子树中查找键值最大的结点，所以，的初值应是要删除结点的左子结点。可见，(3)应填p-＞Rehild。本题把①、②结合在一起进行处理，所以引入了一个中间变量c，用c来存储用于替换p的结点。现在的关键问题是什么条件可以使这两种情况和在一起，因为若删除的结点为叶子结点时，p-＞Rchild与p-＞Lchild都为NULL；若删除的结点有一个子结点时，如果有左子结点，则p-＞Rchild为p-＞Rchild；如果有右子结点，则p-＞Lchild为NULL。当p-＞Lchild不为NULL时，说明是第二种情况，p结点含左子结点，所以c=p-＞Lchild；当p-＞Lchild为 NULL时，说明有两种可能：
   第一：p-＞Rchild也为NULL，则p是叶子结点。
   第二：p-＞Rchild不为NULL，则p是有右子结点的结点。
   这两种情况都可以用c=p-＞Rchild，因为当p是叶子结点的时候用NULL代替p的位置即可，所以第(4)应填p-＞Lehild。在程序中很多地方都出现了变量pp，其实只要仔细看一下前面的程序就知道，pp一直指向的是p结点的前一个结点，即p的父结点，所以(5)的作用是判断p是其父结点的左子结点还是右子结点，(5)应填pp-＞Lchild =p。
转载请注明原文地址:https://www.kaotiyun.com/show/GuDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

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

软考中级

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