C语言二叉排序（搜索）树实例

2023-09-22 20:01:05 63
本文实例为大家分享了C语言二叉排序（搜索）树实例代码，供大家参考，具体内容如下
/**1.实现了递归非递归插入（创建）二叉排序（搜索）树；
分别对应Insert_BinSNode(TBinSNode*T,intk),NonRecursion_Insert_BinSNode(TBinSNode*T,intk);
2.实现了递归非递归查找二叉排序（搜索）树；
分别对应Find_BinSNode(TBinSNode*T,ints),NonRecursion_Find_BinSNode(TBinSNode*T,ints);
3.实现了非递归删除二叉排序（搜索）树；
分别对应Delete_BinSNode()；
4.实现了递归先序、中序、后序遍历二叉排序（搜索）树；
分别对应Pre_Print_BinSNode(TBinSNodeT),In_Print_BinSNode(TBinSNodeT),Post_Print_BinSNode(TBinSNodeT);
*/
#include
#include
typedefstructBinSTreeNode{
intnum;
structBinSTreeNode*lchild,*rchild;
}BinSNode,*TBinSNode;
intEmpty_Tree(TBinSNodeT){
if(!T){
return1;
}else{
return0;
}
}

/*---------------------非递归方法二叉排序树的删除-----------------*/
voidDelete_BinSNode(TBinSNode*T,intdel){
TBinSNodecur,pre,lt,rblast;
cur=*T;
pre=NULL;
//如果二叉排序树为空
if(Empty_Tree(cur)){
printf("Sorry,Treeisnone");
return;
}
//如果二叉排序树不为空，先找到即将删除的元素del.这里再次实现一遍查找，当然也可以修改一下Find类的函数
while(cur&&cur->num!=del){
if(del>cur->num){
pre=cur;
cur=cur->rchild;
}else{
pre=cur;
cur=cur->lchild;
}
}
if(!cur){
printf("Sorry,youwanttodeletethenode,whichisnon-existent");
return;
}
if(cur->num==del){
printf("findthedeletenode,waitaminute.......\n");
}
//如果找到待删除的结点，立刻判断该结点有无左子树

//情况一：待删除结点无左子树
if(!cur->lchild){
if(pre==NULL){
cur=*T;
*T=(*T)->rchild;
free(cur);
return;
}
if(pre->lchild&&pre->lchild->num==del){
pre->lchild=cur->rchild;
free(cur);
return;
}
if(pre->rchild&&pre->rchild->num==del){
pre->rchild=cur->rchild;
free(cur);
return;
}
}
//情况二：待删除的结点有左子树。
if(cur->lchild){
lt=cur->lchild;
//情况2.1：该左子树无右子树
if(!lt->rchild){
if(pre->lchild&&pre->lchild->num==del){
pre->lchild=lt;
free(cur);
return;
}
if(pre->rchild&&pre->rchild->num==del){
pre->rchild=lt;
free(cur);
return;
}
}
//情况2.2:该左子树有右子树
if(lt->rchild){
while(lt->rchild){
rblast=lt;//该左子树中最大的结点的前一个结点.
lt=lt->rchild;
}
cur->num=lt->num;
rblast->rchild=lt->lchild;
free(lt);
return;
}
}
}



/*--------------------递归方法查找二叉排序树-------------------*/
voidFind_BinSNode(TBinSNodeT,ints){
if(s==T->num){
printf("%d\n",T->num);
return;
}
if(s>T->num){
Find_BinSNode(T->rchild,s);
}else{
Find_BinSNode(T->lchild,s);
}
}
/*-------------------非递归方法查找二叉排序树--------------------*/
voidNonRecursion_Find_BinSNode(TBinSNodeT,ints){
if(Empty_Tree(T)){
printf("Treeisnone");
return;
}
while(T&&s!=T->num){
if(s>T->num){
T=T->rchild;
}else{
T=T->lchild;
}
}
if(!T){
printf("Sorry,NotFind!");
exit(0);
}
if(s==T->num){
printf("%d\n",T->num);
}

}
/*-----------------递归方法创建/插入二叉排序树------------------*/
voidInsert_BinSNode(TBinSNode*T,intk){
//intn;
TBinSNodenode;
//scanf("%d",&n);
if(Empty_Tree(*T)){
*T=(TBinSNode)malloc(sizeof(BinSNode));
(*T)->num=k;
(*T)->lchild=(*T)->rchild=NULL;
return;
}else{
if(k>(*T)->num){
Insert_BinSNode(&(*T)->rchild,k);
}else{
Insert_BinSNode(&(*T)->lchild,k);
}
}
}
/*----------------------先序遍历二叉排序树----------------------------------*/
voidPre_Print_BinSNode(TBinSNodeT){
if(T){
printf("%d",T->num);
Pre_Print_BinSNode(T->lchild);
Pre_Print_BinSNode(T->rchild);
}
}
/*-----------------------中序遍历二叉排序树-----------------------------------*/
voidIn_Print_BinSNode(TBinSNodeT){
if(T){
In_Print_BinSNode(T->lchild);
printf("%d",T->num);
In_Print_BinSNode(T->rchild);
}
}

/*-----------------------后序遍历二叉排序树-----------------------------------*/
voidPost_Print_BinSNode(TBinSNodeT){
if(T){
Post_Print_BinSNode(T->lchild);
Post_Print_BinSNode(T->rchild);
printf("%d",T->num);
}
}
/*---------------------非递归创建/插入二叉排序树---------------------------*/
voidNonRecursion_Insert_BinSNode(TBinSNode*T,intk){
//如果为空的二叉排序树
TBinSNodecur,p,t;
t=*T;
if(!*T){
*T=(TBinSNode)malloc(sizeof(BinSNode));
(*T)->num=k;
(*T)->lchild=(*T)->rchild=NULL;
return;
}else{//二叉排序树不为空。
while(t){
if(k>t->num){
cur=t;
t=t->rchild;
}else{
cur=t;
t=t->lchild;
}
}
p=(TBinSNode)malloc(sizeof(BinSNode));
p->num=k;
p->lchild=p->rchild=NULL;
if(k>cur->num){
cur->rchild=p;
}
if(knum){
cur->lchild=p;
}
}
}
intmain(void){
TBinSNodeT=NULL;
intk,s,del;//创建的查找的删除的
while(scanf("%d",&k)&&k){
//Insert_BinSNode(&T,k);
NonRecursion_Insert_BinSNode(&T,k);
}
//scanf("%d",&s);
//Find_BinSNode(T,s);
//NonRecursion_Find_BinSNode(T,s);
Pre_Print_BinSNode(T);
scanf("%d",&del);
Delete_BinSNode(&T,del);
Pre_Print_BinSNode(T);
return0;
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。
C语言二叉排序（搜索）树实例

热门推荐

随机推荐
