2004年上半年下午C语言设计考题

2014年1月2日 作者： 来源：

　　阅读下列函数说明和C函数，将应填入 （n） 处的字句写在答题纸的对应栏内。
[函数5说明]
　　函数DeleteNode(Bitree *r,int e)的功能是：在树根结点指针为r的二叉查找（排序）树上删除键值为e的结点，若删除成功，则函数返回0，否则函数返回-1。二叉查找树结点的类型定义为：
　　typedef struct Tnode{
　　　　int data;
　　　　struct Tnode *Lchild,*Rchild;
　　　　　}*Bitree;
在二叉查找树上删除一个结点时，要考虑三种情况：
○1若待删除的结点p是叶子结点，则直接删除该结点；
○2若待删除的结点p只有一个子结点，则将这个子结点与待删除结点的父结点直接连接，然后删除结点p；
○3若待删除的结点p有两个子结点，则在其左子树上，用中序遍历寻找关键值最大的结点s,用结点s的值代替结点p的值，然后删除结点s,结点s必属于上述○1、○2情况之一。
[函数5]
　　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) { /* 处理情况○3 */
　　　　　　s = (2);pp = p;
　　　　　　while ( (3) ) { pp = s; s = s-> Rchild; }
　　　　　　p->data = s ->data; p = s;
　　　　　　　　}
　　　　/* 处理情况○1、○2*/
　　　　　　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;
　　　}