C language binary sort (search) tree instances

  • 2020-05-30 20:53:45
  • OfStack

The example of this article for you to share C language 2 fork sort (search) tree instance code, for your reference, the specific content is as follows


/**1. We have recursion   Non-recursive insert (create) 2 Cross-sort (search) trees; 
 corresponding Insert_BinSNode(TBinSNode* T,int k),NonRecursion_Insert_BinSNode(TBinSNode* T,int k);
  2. We have recursion   Non-recursive lookup  2 Cross-sort (search) the tree   ; 
 corresponding Find_BinSNode(TBinSNode *T,int s),NonRecursion_Find_BinSNode(TBinSNode *T,int s);
  3.  Non-recursive deletion is implemented  2 Cross-sort (search) trees; 
 corresponding Delete_BinSNode() ;  
  4.  Recursive first order, in order, after the order traversal 2 Cross-sort (search) trees; 
 corresponding 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;
  }
}

/*--------------------- Non-recursive methods  2 Delete of cross-sort tree -----------------*/
void Delete_BinSNode(TBinSNode *T,int del){
  TBinSNode cur,pre,lt,rblast; 
  cur=*T;
  pre=NULL;
  // if 2 The cross-sort tree is empty  
  if(Empty_Tree(cur)){
    printf("Sorry,Tree is none"); 
    return;
  }
// if 2 The cross-sort tree is not empty, so find the element that will be deleted del. Here again 1 Look through, of course, can also be modified 1 Under the Find Function of a class  
  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 the node to be deleted is found, it is immediately judged whether the node has left subtree or not 

  // situation 1 : the node to be deleted has no left subtree  
  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;
    }
  } 
  // situation 2 : the node to be deleted has a left subtree.  
  if(cur->lchild){
    lt=cur->lchild;
    // situation 2.1 : the left subtree has no right subtree  
    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;
      }
    }  
    // situation 2.2: The left subtree has a right subtree  
    if(lt->rchild){
      while(lt->rchild){
        rblast=lt; // Before the largest node in the left subtree 1 A node . 
        lt=lt->rchild; 
      }
      cur->num=lt->num;
      rblast->rchild=lt->lchild;
      free(lt);
      return;
    }  
  }
} 



/*-------------------- Recursive method   To find the  2 Fork sort tree -------------------*/
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);
  }
} 
/*------------------- Non-recursive methods   To find the 2 Fork sort tree --------------------*/
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);
  }

} 
/*----------------- Recursive method   create / insert  2 Fork sort tree ------------------*/ 
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); 
    }
  }  
}
/*---------------------- The first sequence traversal 2 Fork sort tree ----------------------------------*/
void Pre_Print_BinSNode(TBinSNode T){
  if(T){
    printf("%d ",T->num);
    Pre_Print_BinSNode(T->lchild);
    Pre_Print_BinSNode(T->rchild); 
  }
}
/*----------------------- In the sequence traversal 2 Fork sort tree -----------------------------------*/
void In_Print_BinSNode(TBinSNode T){
  if(T){
    In_Print_BinSNode(T->lchild);
    printf("%d ",T->num);
    In_Print_BinSNode(T->rchild); 
  }
}

/*----------------------- After the sequence traversal 2 Fork sort tree -----------------------------------*/
void Post_Print_BinSNode(TBinSNode T){
  if(T){
    Post_Print_BinSNode(T->lchild);
    Post_Print_BinSNode(T->rchild);
    printf("%d ",T->num); 
  }
}
/*--------------------- non-recursive   create / insert  2 Fork sort tree ---------------------------*/
void NonRecursion_Insert_BinSNode(TBinSNode *T,int k){
  // If it's empty 2 Fork sort tree  
  TBinSNode cur,p,t;
  t=*T;
  if(!*T){
    *T=(TBinSNode)malloc(sizeof(BinSNode));
    (*T)->num=k;
    (*T)->lchild=(*T)->rchild=NULL;
    return; 
  }else{     //2 The cross-sort tree is not empty. 
    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;// To create the   To find the   Delete the  
  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;
} 


Related articles: