对二叉排序树的查找都是从根结点开始，则插入失败一定落在叶子上。

A、二叉排序树中，每个结点的关键字都大于等于其左子树中所有结点关键字，都小于其右子树中所有结点关键字

B、二叉排序树中，每个结点的关键字都小于等于其左子树中所有结点关键字，都大于其右子树中所有结点关键字

C、二叉排序树中，每个结点的关键字都小于等于其左右孩子关键字

D、二叉排序树中，每个结点的关键字大于等于其左孩子关键字，都小于其右孩子关键字

【说明】

函数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；

}

【函数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；

}