#include <stdlib.h>
#include <stdio.h>
typedef struct node
{
int k;
struct node *l,*r;
}BT;
BT* INSBT(BT *root,BT *new_T)
{
BT *p = root;
if(root==NULL)
root=new_T;
else
while(p->k!=new_T->k)
if(p->k<new_T->k)
if(p->r==NULL) {
p->r=new_T;
break;
}
else
p=p->r;
else
if(p->l==NULL) {
p->l=new_T;
break;
}
else p=p->l;
return root;
}
BT* CREABT(int n)
{
BT *root,*new_T;
int i,key;
for(root=NULL,i=1;i<=n;i++)
{
scanf("%d",&key);
new_T=(BT*)malloc(sizeof(BT));
new_T->k=key;
new_T->l=new_T->r=NULL;
root=INSBT(root,new_T);
}
return root;
}
BT* SEARBT(BT *root,int key)
{
BT *p;
for(p=root;p!=NULL&&p->k!=key;)
if(p->k<key)
p=p->r;
else p=p->l;
return p;
}
BT* DELBT(BT *root, int key)
{ // 删除key
BT *p,*q,*f;
for(q=NULL,p=root;p!=NULL&&p->k!=key;) // 遍历找到key
{
q=p; // p 是父节点,q是当前节点
if(key<p->k)
p=p->l;
else
p=p->r;
}
if(p->k==key)
{
if(p->l==NULL)
if(q->l==p)
q->l=p->r;else q->r=p->r; // p父节点左子树为空,
else
{ // p父节点左子树不为空
f=p;
for(;p->r!=NULL;q=p,p=p->r); // 沿着左子树的右孩子,右到底
f->k=p->k;
q->r=p->l; // 将得到最右边的节点连接到q节点的左子树
}
free(p);
}
return root;
}
void INBT(BT *root)
{
if(root!=NULL)
{
INBT(root->l);
printf("%d ",root->k);
INBT(root->r);
}
}
int main()
{
BT *root,*p;int n,key;
scanf("%d",&n);
root=CREABT(n);
INBT(root);
scanf("%d",&key);
p=SEARBT(root,key);
if(p==NULL) printf("\nno exit");
else printf("\n%d",p->k);
root=DELBT(root,key);
printf("\n");
INBT(root);
return 0;
}
最后修改:2021 年 12 月 13 日
© 允许规范转载