软件开发|编程技术|编程代码|编程入门先学什么—程序设计语言

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);    */#includestdio.h#includestdlib.htypedef 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(delcur-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(sT-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(sT-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(kt-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(kcur-num){      cur-rchild=p;     }      if(kcur-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;} 

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