数据结构实验—-二叉排序树（查找树BST)的操作（查找，插入，删除）//二叉树结点类型为整型的情况

#include <stdio.h>
#include <stdlib.h>
#define KeyType char
typedef int KeyType;
typedef struct tree{
struct tree *left;
struct tree *right;
KeyType key;
} BSTNode, * BSTree;

BSTree insertBST(BSTree tptr,KeyType key)
{
BSTree f,p=tptr;
while(p)
{
if(p->key==key)
return tptr;
f=p;
p=(key<p->key)?p->left:p->right;
}
p=(BSTree )malloc(sizeof(BSTNode));
p->key=key; p->left=p->right=NULL;
if(tptr==NULL)
tptr=p;
else
if(key<f->key)
f->left=p;
else
f->right=p;
return tptr;
}

BSTree createBST()
{
BSTree t=NULL;
KeyType key;
scanf("%d",&key);
while(key!=-1)
{
t=insertBST(t,key);
scanf("%d",&key);
}
return t;
}

void inorder_btree(BSTree root)
{
BSTree p=root;
if(p!=NULL){
inorder_btree(p->left );
printf("%6d",p->key );
inorder_btree(p->right );
}
}

int searchBST(BSTree t,KeyType key)
{
if(key==t->key)
return 1;
if(t==NULL)
return 0;
if(key<t->key)
return searchBST(t->left,key);
else
return searchBST(t->right,key);
}

BSTree deleteBST(BSTree tptr,KeyType key)
{
BSTree p,tmp,parent=NULL;
p=tptr;
while(p)
{
if(p->key==key)
break;
parent=p;
p=(key<p->key)?p->left:p->right;
}
if(!p) return NULL;
tmp=p;
if(!p->right&&!p->left)
{
if(!parent)
tptr=NULL;
else if(p==parent->right)
parent->right=NULL;
else
parent->left=NULL;
free(p);
}
else if(!p->right)
{
p=p->left;
if(!parent)
tptr=p;
else if(tmp==parent->left)
parent->left=p;
else
parent->right=p;
free(tmp);
}
else if(!p->left)
{
p=p->right;
if(!parent)
tptr=p;
else if(tmp==parent->left)
parent->left=p;
else
parent->right=p;
free(tmp);
}
else if(p->right&&p->left)
{
parent=p;
p=p->right;
while(p->left)
{
parent=p;
p=p->left;
}
tmp->key=p->key;
if(p==parent->left)
parent->left=NULL;
else
parent->right=NULL;
free(p);
}
return tptr;
}

int main()
{
KeyType key;
int flag,test;
char cmd;
BSTree root;
printf("\n\n--------------------------------------------------------\n");
printf("\n****欢迎测试和修正本程序！本程序用以研究二叉排序树。****\n");
printf("\n--------------------------------------------------------\n\n");
do
{
printf("\n\n 请选择你要执行的操作:\n\n");
printf(" C......创建一棵二叉排序树\n");
printf(" A......结束本程序\n\n");
flag=0;
do
{
if(flag!=0)
printf("选择操作错误！请重新选择！\n");
fflush(stdin);
scanf("%c",&cmd);
flag++;
}while(cmd!='c'&&cmd!='C'&&cmd!='a'&&cmd!='A');
if(cmd=='c'||cmd=='C')
{
printf("请输入你所要创建的二叉树的结点的值，以-1结束：\n");
root=createBST();
do
{
flag=0;
printf("\n\n中序遍历二叉树："); inorder_btree(root);
printf("\n\n\t请选择你要对这棵二叉树所做的操作:\n\n");
//printf("\tz,Z......中序遍历这棵二叉树\n");
printf("\tS......查找你想要寻找的结点\n");
printf("\tI......插入你想要插入的结点\n");
printf("\tD......删除你想要删除的结点\n");
printf("\tQ......结束对这棵二叉树的操作\n\n");
do
{
if(flag!=0)
printf("选择操作错误！请重新选择！\n");
fflush(stdin);
scanf("%c",&cmd);
flag++;
}while(cmd!='s'&&cmd!='S'&&cmd!='i'&&cmd!='I'&&cmd!='d'&&cmd!='D'&&cmd!='q'&&cmd!='Q');
switch(cmd)
{

case 's': 
case 'S':
printf("请输入你要查找结点的关键字：\n");
scanf("%d",&key);
test=searchBST(root,key);
if(test==0)
printf("\n对不起，你所差找的结点%d不存在!\n",key);
else
printf("\n成功找到结点%d.\n",key);
break;
case 'i':
case 'I':
printf("请输入你要插入结点的关键字：\n");
scanf("%d",&key);
root=insertBST(root,key);
break;
case 'd':
case 'D':
printf("请输入你要删除结点的关键字：\n");
scanf("%d",&key);
root=deleteBST(root,key);
if(root==NULL)
printf("\n对不起，你所删除的结点%d不存在!\n",key);
else
printf("\n成功删除结点%d.\n",key);
break;
}
}while(cmd!='q'&&cmd!='Q');
}
}while(cmd!='a'&&cmd!='A');
printf("\n\n----------------------------\n\n");
printf("****谢谢使用！欢迎指正！****\n\n");
printf("----------------------------\n\n");
printf("作者：杨寅 学号：07082107 时间：2008.12.16\n\n\n\n");
return 0;
}

也许您喜欢下面的文章，不要错过哦: