2. 计算机
  3. [函数] int DeleteNode(Bitree *r，int e){ Bitree p=* r，pp，s，c； while((1)){/ * 从树根结点出发查找键值为e的结点 * /

[函数] int DeleteNode(Bitree *r，int e){ Bitree p=* r，pp，s，c； while((1)){/ * 从树根结点出发查找键值为e的结点 * /

admin2005-03-15  77
问题 [函数]
      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-＞dara=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
解析 本程序的功能是删除二叉查找树的一个结点。二叉查找树又称二叉排序树(binary sort tree)。一棵二叉查找树或者是一棵空树，应满足以下递归条件：
   ①查找树的左、右子树各是一棵查找树。
   ②若查找树的左子树非空，则其左子树上的各结点值均小于根结点的值。
   ③若查找树的右子树非空，则其右子树上的各结点值均大于根结点的值。
   例如，图4-8就是一棵二叉查找树。
   
   题目中对怎样删除结点做了比较详细的说明。
   第一种情况是删除叶子结点。叶子结点可以直接删除，这点很好理解，因为叶子结点删除后并不会打乱查找树的顺序，也就是说把图4-8中的“20”结点删除，剩下的还是一棵查找树。
   第二种情况是删除只有1个子结点的结点，只需把其子结点代替父结点即可，也就是说若要删除图4-8中的“56”结点，只需把“51”移至“56”位置即可，若“51”下有子树，子树结构不变。
   第三种情况要复杂一点，要用到二叉查找树的一些性质，就是结点右子树的所有结点都大于根结点，左子树所有结点都小于根结点。所以，当删除有左右子树的结点时，要在左子树找最大的结点来替换被删结点。也就是说若要删除图4-8中的“89”结点，首先要把“56”搬到“89”的位置，然后用第二种情况规则，把“51”调整到原来56的位置。
   以下具体分析程序。
   第一句是变量的声明以及赋初值，p指向二叉查找树的根。接下来是一个循环，从注释部分可以知道，此循环的功能是查找键值为e的结点。循环内有判断条件，当e＜p－＞ data时，进入左子树查找，否则到右子树中查找。很明显没有关于找到结点的处理代码，也就是说循环内部只处理了没找到结点的情况，所以循环条件应是当找到键值为e的结点时退出循环。同时应注意一个隐含的限制条件，就是当p=NULL时，表示已经查找完毕，也不用进入循环了。所以(1)空应填p && p-＞data !=e。
   接下来的if程序段是处理第③种情况的。由循环中的“s=s－＞Rchild；”可以看出，s用在要删结点的左子树中查找键值最大的结点。所以s的初值应是要删除结点的左子结点。所以，(2)空应填p-＞Lchild。
   结合前面提到的对第③条规则的描述以及二叉查找树的规则可知，要找的结点s应是左子树最右的结点，即右子结点为NULL的结点。所以(3)空应填S-＞Rchild。
   接着对①、②处理。这里并没有把①、②处理分开进行，而是合在一起进行处理。这里引入了一个中间变量c，用c来存储用于替换p的结点。
   现在分析怎样的条件可以使这2种情况合在一起。因为当要删除的结点为叶子结点时，p-＞Lchild与p-＞Rchild都为NULL；当要删除的结点有1个子结点时，如果有左子结点，则p-＞Rchild为NULL；如果有右子结点，则p-＞Lchild为NULL。所以当 p-＞Lchild不为NULL时，说明是第二种情况，p结点含左子结点，c=p-＞Lchild。当 p-＞Lchild为NULL时，说明有2种可能：第一，p-＞Rchild也为NULL，则p是叶子结点；第二，p-＞Rchild不为NULL，则P是有右子结点的结点。但这2种情况都可以用c=p-＞Rchild，因为当p是叶子结点的时候用NULL代替p的位置即可，所以(4)空应填p-＞Lchild。在程序中很多地方都用到了变量pp。pp一直指向的是p结点的前一个结点，即p的父结点，所以(5)空的作用是判断p是其父结点的左子结点还是右子结点，即(5)空应填pp-＞Lchild=p。
转载请注明原文地址:https://kaotiyun.com/show/VyDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

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

软考中级

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