C语言二叉排序(搜索)树实例
本文实例为大家分享了C语言二叉排序(搜索)树实例代码,供大家参考,具体内容如下
创新互联建站是专业的平桂网站建设公司,平桂接单;提供成都网站制作、网站设计,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行平桂网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!
/**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#include 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 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语言二叉排序(搜索)树实例
转载来于:http://myzitong.com/article/gdpgop.html