C语言：设计算法在二叉排序树中删除特定值的结点

Question

这是我们这次考试的 题目。 谁能帮我用C语言写出来啊
感激不尽啊 要能在C语言上实现的 发我邮箱最好了 [email protected] 或者直接把代码写在问问上也可以，
谢谢大家了 一定要能实现的哦。

Answer 1

void DelBSTNode(BSTree *Tptr，KeyType key)
{//在二叉排序树*Tptr中删去关键字为key的结点
BSTNode *parent=NUll，*p=*Tptr，*q，*child；
while(p){ //从根开始查找关键字为key的待删结点
if(p->key==key) break；//已找到，跳出查找循环
parent=p； //parent指向*p的双亲
p=(key<p->key)?p->lchild：p->rchild； //在关p的左或右子树中继续找
}
if(!p) return； //找不到被删结点则返回
q=p； //q记住被删结点*p
if(q->lchild&&q->rchild) //*q的两个孩子均非空，故找*q的中序后继*p
for(parent=q，p=q->rchild； p->lchild； parent=p，p=p=->lchild)；
//现在情况(3)已被转换为情况(2)，而情况(1)相当于是情况(2)中child=NULL的状况
child=(p->lchild)?p->lchild：p->rchild；//若是情况(2)，则child非空；否则child为空
if(!parent) //*p的双亲为空，说明*p为根，删*p后应修改根指针
*Tptr=child； //若是情况(1)，则删去*p后，树为空；否则child变为根
else{ //*p不是根，将*p的孩子和*p的双亲进行连接，*p从树上被摘下
if(p==parent->lchild) //*p是双亲的左孩子
parent->lchild=child； //*child作为*parent的左孩子
else parent->rchild=child； //*child作为 parent的右孩子
if(p!=q) //是情况(3)，需将*p的数据复制到*q
q->key=p->key； //若还有其它数据域亦需复制
} //endif
free(p)； /释放*p占用的空间
} //DelBSTNode

Answer 2

//与他人分享自己的程序，开源
#include <stdio.h>
#include <stdlib.h>
typedef int KeyType;
typedef struct node
{
KeyType key ;
struct node *lchild,*rchild;
}BSTNode, *BSTree;

void InsertBST(BSTree *bst, KeyType key)
{
BSTree s;
if (*bst == NULL)
{
s=(BSTree)malloc(sizeof(BSTNode));
s-> key=key;
s->lchild=NULL;
s->rchild=NULL;
*bst=s;
}
else
if (key < (*bst)->key)
InsertBST(&((*bst)->lchild), key);
else
if (key > (*bst)->key)
InsertBST(&((*bst)->rchild), key);
}

BSTNode * DelBST(BSTree t, KeyType k)
{
BSTNode *p, *f,*s ,*q;
p=t;
f=NULL;
while(p)
{
if(p->key==k ) break;
f=p;
if(p->key>k)
p=p->lchild;
else
p=p->rchild;
}
if(p==NULL) return NULL;
if(p->lchild==NULL)
{
if(f==NULL)
t=p->rchild;
else
if(f->lchild==p)
f->lchild=p->rchild ;
else
f->rchild=p->rchild ;
free(p);
}
else
{
q=p;
s=p->lchild;
while(s->rchild)
{
q=s;
s=s->rchild;
}
if(q==p)
q->lchild=s->lchild ;
else
q->rchild=s->lchild;
p->key=s->key;
free(s);
}
return t;
}

void CreateBST(BSTree *bst)
{
int ENDKEY=0,key;
*bst=NULL;
scanf("%d", &key);
while (key!=ENDKEY)
{
InsertBST(bst, key);
scanf("%d", &key);
}
}

void PreOrder(BSTree root)
{
if (root!=NULL)
{
printf("%d ",root->key);
PreOrder(root->lchild);
PreOrder(root->rchild);
}
}

void main()
{
BSTree T;
int k;
printf("建立二叉排序树，请输入序列以0结束输入:\n");
CreateBST(&T);
printf("先序遍历输出序列为:");
PreOrder(T);
printf("\n输入你要删除的数:");
scanf("%d",&k);
T=DelBST(T,k);
if(T==NULL)
printf("无此数");
else
printf("先序遍历输出这个序列为:");
PreOrder(T);
printf("\n");
}