Sunday, October 2, 2011

Data Structure C program Binary Search Tree Dev c++


Data Structures in C Program Binary Search Tree


 #include <stdio.h>  
 struct bstree{  
     int info;  
     struct bstree* left;  
     struct bstree* right;  
     };  
 typedef struct bstree* node;  
 node root;  
 node create(int x)  
 {  
    node abh;  
    abh=(node)malloc(sizeof(struct bstree));  
    if(abh==NULL)  
    {  
    printf("OUT OF MEMORY!!!!FATAL ERROR");  
    exit(0);  
    }  
    else  
    {  
      abh->info=x;  
      abh->left=NULL;  
      abh->right=NULL;  
    }  
    return abh;  
 }  
 void insert(int x)  
 {  
    node at=create(x);  
    if(root==NULL)  
    {  
     root=at;  
    }  
    else  
    {  
      node prev=NULL;  
      node cur=root;  
      while(cur!=NULL)  
      {  
       prev=cur;  
       if(x>cur->info)  
       cur=cur->right;  
       else  
       cur=cur->left;  
      }  
      if(x>prev->info)  
       prev->right=at;  
      else  
       prev->left=at;  
    }  
 }  
 node findmin(node av)  
 {  
    if(av->left!=NULL && av->right==NULL)  
    return av->left;  
    else   
    return av;  
 }  
 void delete(int x)  
 {  
      node prev=NULL;  
      node cur=root;  
      node anj;  
      while(cur!=NULL && cur->info!=x)  
      {  
       prev=cur;  
       if(x>cur->info)  
       cur=cur->right;  
       else  
       cur=cur->left;  
      }  
      if(cur==NULL)  
      {  
      printf("NOT FOUND");  
      }  
      else  
      {  
        printf("Deleting %d ",cur->info);  
           if(cur->left && cur->right )//TWO CHILDREN  
           {  
            anj=cur->right;//move right  
            node ver=cur;//previous  
            if(anj->left==NULL)//if moving to extreme left is not possible  
            {  
          cur->info=anj->info;  
          cur->right=anj->right;  
          free(anj);  
         }else{  
         while(anj->left!=NULL)//move to extreme left  
         {   
          ver=anj;  
          anj=anj->left;  
         }  
         cur->info=anj->info;  
         ver->left=NULL;  
         free(anj);  
         }  
           }  
           else  
           {  
                  if(cur->right!=NULL && cur->left==NULL)//only right  
              {  
             //printf("c2");  
                    if(cur->info>prev->info)  
                       prev->right=cur->right;  
                    else  
                       prev->left=cur->right;  
                    free(cur);  
                    return;  
               }else if(cur->right==NULL && cur->left!=NULL)//only left  
               {  
              //printf("c3");  
              if(cur->info>prev->info)  
                       prev->right=cur->left;  
                   else  
                       prev->left=cur->left;  
                    free(cur);  
           }   
           else if(cur->right==NULL && cur->left==NULL)//leaf  
              {  
               //printf("c4");  
                       if(cur->info>prev->info)  
                       prev->right=NULL;  
                       else  
                       prev->left=NULL;  
                       free(cur);  
               }  
           }  
      }      
 }  
 void inorder(node root)  
 {  
  if(root)  
  {  
  inorder(root->left);  
  printf("[%d] ", root->info);  
  inorder(root->right);  
  }  
 }  
 node insert_rec(node r,int data)  
 {  
  if(r==NULL)  
  {  
   r=create(data);  
   }  
  else if(data>r->info)  
   r->right=insert_rec(r->right,data);//r->right is important to create link or else isolated node is made  
  else  
   r->left=insert_rec(r->left,data);  
  return r;//good  
 }  
 int main()  
 {  
   root=NULL;  
   /*add_node(5);  
   add_node(1);  
   add_node(6);*/  
   root=insert_rec(root,5);//root= for first node to create link  
   insert_rec(root,1);  
   insert_rec(root,6);  
   insert_rec(root,3);  
   insert_rec(root,4);  
   insert_rec(root,-1);  
   insert_rec(root,8);  
   delete(6);  
   delete(1);  
   insert_rec(root,100);  
   insert_rec(root,-3);   
   delete(6);  
   delete(5);  
   inorder(root);  
   getch();  
 }  

No comments:

Post a Comment

Google+ Followers