大佬教程收集整理的这篇文章主要介绍了C语言二叉排序(搜索)树实例,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
本文实例为大家分享了C语言二叉排序(搜索)树实例代码,供大家参考,具体内容如下
/**1.实现了递归 非递归插入(创建)二叉排序(搜索)树; 分别对应InserT_Binsnode(TBinsnode* T,int k),NonRecursion_InserT_Binsnode(TBinsnode* T,int k); 2.实现了递归 非递归查找 二叉排序(搜索)树 ; 分别对应Find_Binsnode(TBinsnode *T,int s),NonRecursion_Find_Binsnode(TBinsnode *T,int s); 3. 实现了非递归删除 二叉排序(搜索)树; 分别对应delete_Binsnode(); 4. 实现了递归先序、中序、后序遍历二叉排序(搜索)树; 分别对应Pre_PrinT_Binsnode(TBinsnode T),In_PrinT_Binsnode(TBinsnode T),Post_PrinT_Binsnode(TBinsnode T); */ #include<stdio.h> #include<stdlib.h> typedef struct BinstreeNode{ int num; struct BinstreeNode *lchild,*rchild; }Binsnode,*TBinsnode; int Empty_Tree(TBinsnode T){ if(!T){ return 1; }else{ return 0; } } /*---------------------非递归方法 二叉排序树的删除-----------------*/ voID delete_Binsnode(TBinsnode *T,int del){ TBinsnode cur,pre,lt,rblast; cur=*T; pre=NulL; //如果二叉排序树为空 if(Empty_Tree(cur)){ printf("Sorry,Tree is none"); 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,you want to delete the node,which is non-existent"); return; } if(cur->num==del){ printf("find the delete node,wait a minute.......\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; } } } /*--------------------递归方法 查找 二叉排序树-------------------*/ voID Find_Binsnode(TBinsnode T,int s){ 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); } } /*-------------------非递归方法 查找二叉排序树--------------------*/ voID NonRecursion_Find_Binsnode(TBinsnode T,int s){ if(Empty_Tree(T)){ printf("Tree is none"); return; } while(T && s!=T->num ){ if(s>T->num){ T=T->rchild; }else{ T=T->lchild; } } if(!T){ printf("Sorry,Not Find!"); exit(0); } if(s==T->num){ printf("%d\n",T->num); } } /*-----------------递归方法 创建/插入 二叉排序树------------------*/ voID InserT_Binsnode(TBinsnode *T,int k){ // int n; TBinsnode node; // 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); } } } /*----------------------先序遍历二叉排序树----------------------------------*/ voID Pre_PrinT_Binsnode(TBinsnode T){ if(T){ printf("%d ",T->num); Pre_PrinT_Binsnode(T->lchild); Pre_PrinT_Binsnode(T->rchild); } } /*-----------------------中序遍历二叉排序树-----------------------------------*/ voID In_PrinT_Binsnode(TBinsnode T){ if(T){ In_PrinT_Binsnode(T->lchild); printf("%d ",T->num); In_PrinT_Binsnode(T->rchild); } } /*-----------------------后序遍历二叉排序树-----------------------------------*/ voID Post_PrinT_Binsnode(TBinsnode T){ if(T){ Post_PrinT_Binsnode(T->lchild); Post_PrinT_Binsnode(T->rchild); printf("%d ",T->num); } } /*---------------------非递归 创建/插入 二叉排序树---------------------------*/ voID NonRecursion_InserT_Binsnode(TBinsnode *T,int k){ //如果为空的二叉排序树 TBinsnode cur,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(k<cur->num){ cur->lchild=p; } } } int main(voID){ TBinsnode T=NulL; int k,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); return 0; }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持编程小技巧。
以上是大佬教程为你收集整理的C语言二叉排序(搜索)树实例全部内容,希望文章能够帮你解决C语言二叉排序(搜索)树实例所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。