首页 > 代码库 > 二叉排序树的基本操作

二叉排序树的基本操作

2024-08-03 18:37:30   216人阅读

#include<stdio.h>
#include<malloc.h>
typedef struct node
{/*定义二叉排序树的结构*/
int  key;
struct node *lchild;
struct node *rchild;
}BSTnode, *BSTree;
void InsertBST( BSTree *bst,int 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);
}
void CreateBST(BSTree *bst)
{/*创建二叉排序树*/
int  key;
*bst=NULL;
scanf("%d",&key);
while(key!=-1)
{
InsertBST(bst ,key);
scanf("%d",&key);
}
}
int SearchBST(BSTree bst,int key)
{/*二叉排序树查找,找到后返回1.否则返回0*/
if(!bst)
return 0;
else if(bst->key==key)
return 1;
else if(bst->key>key)
return SearchBST(bst->lchild,key);
else
return SearchBST(bst->rchild,key);
}
BSTnode *DelBST(BSTree bst,int k)
{//删除二叉排序树结点
BSTnode *p,*f,*s,*q;
p=bst;
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 bst;
if(p->lchild==NULL)
{
if(f==NULL)
bst=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 bst;
}
void PrintTree(BSTree *bst)
{
if(*bst!=NULL)
{
printf("%d ",(*bst)->key);
PrintTree(&(*bst)->lchild);
PrintTree(&(*bst)->rchild);
}
}
int main(void)
{
BSTree bst,t;
int n,key;
int m;
printf("请输入一组数据创建二叉排序树，当为-1时结束:\n");
CreateBST(&bst);
printf("\n");
printf("输出二叉排序树:\n");
PrintTree(&bst);
printf("\n");
    printf("请输入要查找的数据key:\n");
scanf("%d",&key);
printf("%d",SearchBST(bst,key));
printf("\n");
printf("请输入要删除的结点m:\n");
scanf("%d",&m);
t=DelBST(bst,m);
PrintTree(&t);
printf("\n");
return 0;
}











二叉排序树的基本操作


联系
我们