C语言二叉排序(搜索)树实例

时间:2021-05-20

本文实例为大家分享了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;}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。

声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

相关文章