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;}