本文实例为大家分享了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;}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。
孤单寂寞与被遗弃感是最可怕的贫穷
