数据结构_数据结构的
数据结构由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构的”。
数据结构】二叉排序树的建立，查找，插入和删除实践题 /*sy53.c*/
#include
#include
typedef int KeyType;
typedef struct node{
KeyType key;
struct node *lchild,*rchild;
}BSTNode;
typedef BSTNode *BSTree;
BSTree CreateBST(void);
void SearchBST(BSTree T,KeyType Key);
void InsertBST(BSTree *Tptr,KeyType Key);
void DelBSTNode(BSTree *Tptr,KeyType Key);
void InorderBST(BSTree T);
main()
{BSTree T;
char ch1,ch2;
KeyType Key;
printf(“建立一棵二叉排序树的二叉链表存储n”);
T=CreateBST();
ch1='y';
while(ch1=='y' || ch1=='Y')
{printf(“请选择下列操作：n”);
printf(“1------------------更新二叉排序树存储n”);
printf(“2------------------二叉排序树上的查找n”);
printf(“3------------------二叉排序树上的插入n”);
printf(“4------------------二叉排序树上的删除n”);
printf(“5------------------二叉排序树中序输出n”);
printf(“6------------------退出n”);
scanf(“n%c”,&ch2);
switch(ch2)
{case '1':T=CreateBST();break;
case '2':printf(“n请输入要查找的数据：”);
scanf(“n%d”,&Key);
SearchBST(T,Key);
printf(“查找操作完毕。n”);break;
case '3': printf(“n请输入要插入的数据：”);
scanf(“n%d”,&Key);
InsertBST(&T,Key);
printf(“插入操作完毕。n”);break;
case '4': printf(“n请输入要删除的数据：”);
scanf(“n%d”,&Key);
DelBSTNode(&T,Key);
printf(“删除操作完毕。n”);break;
case '5': InorderBST(T);
printf(“n二叉排序树输出完毕。n”);break;
case '6':ch1='n';break;
default:ch1='n';
}
}
}
BSTree CreateBST(void)
{BSTree T;
KeyType Key;
T=NULL;
printf(“请输入一个关键字(输入0时结束输入)：n”);scanf(“%d”,&Key);
while(Key)
{InsertBST(&T,Key);
printf(“请输入下一个关键字(输入0时结束输入)：n”);scanf(“n%d”,&Key);
}
return T;
}
void SearchBST(BSTree T, KeyType Key)
{ BSTNode *p=T;
while(p)
{if(p->key==Key)
{printf(“已找到n”);
return;
}
p=(Key
key)? p->lchild:p->rchild;
}
printf(“没有找到n”);
}
void InsertBST(BSTree *T,KeyType Key)
{BSTNode *f,*p;
p=(*T);
while(p)
{if(p->key==Key)
{printf(“树中已有Key不需插入n”);
return;
}
f=p;
p=(Key
key)?p->lchild:p->rchild;
}
p=(BSTNode*)malloc(sizeof(BSTNode));
p->key=Key;
p->lchild=p->rchild=NULL;
if((*T)==NULL)(*T)=p;
else if(Keykey)f->lchild=p;
else f->rchild=p;
}/*InsertBST*/
void DelBSTNode(BSTree *T,KeyType Key)
{BSTNode *parent=NULL, *p, *q,*child;
p=*T;
while(p)
{if(p->key==Key)break;
parent=p;
p=(Key
key)?p->lchild:p->rchild;
}
if(!p){printf(“没有找到要删除的结点n”);return;}
q=p;
if(q->lchild && q->rchild)
for(parent=q,p=q->rchild;p->lchild;parent=p,p=p->lchild);child=(p->lchild)?p->lchild:p->rchild;
if(!parent)*T=child;
else {if(p==parent->lchild)
parent->lchild=child;
else parent->rchild=child;
if(p!=q)
q->key=p->key;
}
free(p);
}
void InorderBST(BSTree T){ if(T!=NULL)
{InorderBST(T->lchild);printf(“%5d”,T->key);InorderBST(T->rchild);}
}
