【说明】 函数DeleteNode(Bitree*r，inte)的功能是：在树根节点指针为r的二叉查找(排序)树上删除键值为e的节点，若删除成功，则函数返回0，否则函数返回-1。二叉查找树节点的类型定义为： typedef struct Tnode{int data;/*节点的键值*/struct Tnode *Lchild,*Rchiid;/*指向左、右子树的指针*/ }*Bitree; 在二叉查找树上删除一个节点时，要考虑3种情况。 ①若待删除的节点p是叶子节点，则直接删除该节点。 ②若待删除的节点p只有一个子节点，则将这个子节点与待删除节点的父节点直接连接，然后删除节点。 ③若待删除的节点p有两个子节点，则在其左子树上，用中序遍历寻找关键值最大的节点 s，用节点s的值代替节点p的值，然后删除节点s，节点s必属于上述①、②情况之一。 【函数5-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-＞Rehild;}if(!p)retrn -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; }
