程序填空题：二叉排序树删除结点
```c++
#include
using namespace std;
typedef struct ElemType{
int key;
}ElemType;
typedef struct BSTNode{
ElemType data;
BSTNode *lchild,*rchild;
}BSTNode,*BSTree;
int flag=1;
void InsertBST(BSTree &T,ElemType e ) ;//实现细节隐藏
void CreateBST(BSTree &T ) ;//实现细节隐藏
void InOrderTraverse(BSTree &T)；//中序遍历，实现细节隐藏
void DeleteBST(BSTree &T,char key) {
BSTree p=T;BSTree f=NULL;
BSTree q;
BSTree s;
while(p){
if (p->data.key == key) break;
f=p;
if (p->data.key> key) p=p->lchild;
else p=p->rchild;
}
if(!p) @@[return](2);
if ((p->lchild)&& (p->rchild)) {
q = p;
s = p->lchild;
while (s->rchild)
{q = s; s = s->rchild;}
p->data= s->data;
if(q!=p)@@[q->rchild = s->lchild](2);
else @@[q->lchild = s->lchild](2);
delete s;
}
else{
if(!p->rchild) { q = p; p = p->lchild; }
else if(!p->lchild) { q = p; p = p->rchild; }
if(!f) @@[T=p](2);
else if (q==f->lchild) @@[f->lchild = p](2);
else @@[f->rchild = p](2);
delete q;
}
}
int main()
{
BSTree T;
CreateBST(T);
int key;
cin>>key;
DeleteBST(T,key);
InOrderTraverse(T);
}
```
答案：
第1空：return
第2空：q->rchild = s->lchild
第3空：q->lchild = s->lchild
第4空：T=p
第5空：f->lchild = p
第6空：f->rchild = p
#include
using namespace std;
typedef struct ElemType{
int key;
}ElemType;
typedef struct BSTNode{
ElemType data;
BSTNode *lchild,*rchild;
}BSTNode,*BSTree;
int flag=1;
void InsertBST(BSTree &T,ElemType e ) ;//实现细节隐藏
void CreateBST(BSTree &T ) ;//实现细节隐藏
void InOrderTraverse(BSTree &T)；//中序遍历，实现细节隐藏
void DeleteBST(BSTree &T,char key) {
BSTree p=T;BSTree f=NULL;
BSTree q;
BSTree s;
while(p){
if (p->data.key == key) break;
f=p;
if (p->data.key> key) p=p->lchild;
else p=p->rchild;
}
if(!p) @@[return](2);
if ((p->lchild)&& (p->rchild)) {
q = p;
s = p->lchild;
while (s->rchild)
{q = s; s = s->rchild;}
p->data= s->data;
if(q!=p)@@[q->rchild = s->lchild](2);
else @@[q->lchild = s->lchild](2);
delete s;
}
else{
if(!p->rchild) { q = p; p = p->lchild; }
else if(!p->lchild) { q = p; p = p->rchild; }
if(!f) @@[T=p](2);
else if (q==f->lchild) @@[f->lchild = p](2);
else @@[f->rchild = p](2);
delete q;
}
}
int main()
{
BSTree T;
CreateBST(T);
int key;
cin>>key;
DeleteBST(T,key);
InOrderTraverse(T);
}
```
答案：
第1空：return
第2空：q->rchild = s->lchild
第3空：q->lchild = s->lchild
第4空：T=p
第5空：f->lchild = p
第6空：f->rchild = p
