Monday, June 18, 2012

binary search tree C program !!

Below is the complete working C code with all operations in Binary Search Tree.
#include<stdio.h>
#include<malloc.h>

struct bst
{
 int info;
 struct bst *left;
 struct bst *right;
};


void delete(struct bst *root, int key);
struct bst *find_min(struct bst *node);
struct bst *find_max(struct bst *node);
struct bst *insert(struct bst *node, int key);
void print_postorder(struct bst *root);
void print_preorder(struct bst *root);
void print_inorder(struct bst *root);
int height(struct bst *root);

//deleting the element which handles three cases
//1. deleting node has no leaf nodes
//2. deleting node has one child(left or right)
//3. deleting node has two childs
void delete(struct bst *root, int key)
{
 struct bst *current;
 struct bst *prev;
 int found = 0;
 if(root == NULL)
 {
  printf("The BST is empty\n");
  return;
 }
 current = root;
 while(current!=NULL)
 {
  if(current->info == key)
  {
   found = 1;
   break;
  }
  else
  {
   prev = current;
   if(current->info >= key)
    current = current->left;
   else
    current = current->right;
  }
 }
 if(!found)
 {
  printf("given key element is not in the BST\n");
  return;
 }

 //leaf node , no left n right childs
 if((current->left == NULL) && (current->right == NULL))
 {
  if(prev->left == current)
   prev->left = NULL;
  else
   prev->right = NULL;
  free(current);
 }

 //single child node (either left or right child)
 if(current->left == NULL && current->right != NULL)
 {
  if(prev->left == current)
   prev->left = current->right;
  else
   prev->right = current->right;
  free (current);
 }

 if(current->right == NULL && current->left!=NULL)
 {
   if(prev->left = current)
    prev->left = current->left;
   else
    prev->right = current->left;
   free(current);
 }

 // need to handle the very complex case(node with both left n right childs)
 if(current->left != NULL && current->right != NULL)
 {
  struct bst *tmp = current->right;
  if(tmp->left == NULL && tmp->right == NULL)
  {
   current->info = tmp->info;
   free(tmp);
   current->right = NULL;
  }
  else if(current->right->left != NULL)
  {
   struct bst *left_current = current->right;
   struct bst *left_current_prev = current->right->left;
   while(left_current->left != NULL)
   {
    left_current_prev = left_current;
    left_current = left_current->left;
   }
   current->info = left_current->info;
   free(left_current);
   left_current_prev->left = NULL;
  }
  else
  {
   struct bst *temp;
   temp = current->right;
   current->info = temp->info;
   current->right = temp->right;
   free(temp);
  }
 }
}

//finding the min value
struct bst *find_min(struct bst *node)
{
 if(node == NULL)
  return NULL;
 if(node->left == NULL)
  return node;
 else
  return find_min(node->left);
}


//finding the max value
struct bst *find_max(struct bst *node)
{
 if(node!=NULL)
 {
  while(node->right!=NULL)
   node = node->right;
 }
 return node;
}

//adding the new element to the BST
struct bst *insert(struct bst *node, int key)
{
 if(node == NULL)
 {
 //creating the new node with the key and left n right sub nodes empty
  node = (struct bst *)malloc(sizeof(struct bst));
  node->info = key;
  node->left = node->right = NULL;
 }
 else if(node->info >= key)
  node->left = insert(node->left, key);
 else
  node->right= insert(node->right, key);
 return node;
}

//printing post order (LRP)
void print_postorder(struct bst *root)
{
 struct bst *temp = root;
 if(temp!=NULL)
 {
  print_postorder(temp->left);
  print_postorder(temp->right);
  printf("%d ",temp->info);
 }
}

//printing preorder(PLR)
void print_preorder(struct bst *root)
{
 struct bst *temp = root;
 if(temp!=NULL)
 {
  printf("%d ",temp->info);
  print_preorder(temp->left);
  print_preorder(temp->right);
 }
}

//printing inorder (LPR)
void print_inorder(struct bst *root)
{
 struct bst *temp = root;
 if(temp!=NULL)
 {
  print_inorder(temp->left);
  printf("%d ",temp->info);
  print_inorder(temp->right);
 }
}
// to find the height of the tree
int height(struct bst *root)
{
    struct bst *temp = root;
    int leftH = 0;
    int rightH = 0;
    if(temp == NULL)
        return 0;
    if(temp->left)
        leftH = height(temp->left);
    if(temp->right)
        rightH = height(temp->right);
    return leftH >rightH ? leftH+1 : rightH+1;
}


int main()
{
 struct bst *root=NULL;
 struct bst *tmp=NULL;
 int i,n,key,option;
 printf("Enter the no. elements in the BST\n");
 scanf("%n",&n);
 printf("Enter the list of elements in the BST\n");
 for(i=0;i<n;i++)
 {
  scanf("%d",&key);
  root = insert(root,key);
 }
 printf("Below are the possible opetaions you can performe in the above created BST\n");
 printf("1. Insert\n2. Delete\n3. In-Order\n4. Pre-Order\n5. Post-Order\n6. Find Minimum\n7. Find Max\n8. height\n other value for exit");
 scanf("%d,&option");
 while(1)
 {
  switch(option)
  {
   case 1:
     printf("Enter the valeu to insert into the BST\n");
     scanf("%d",&key);
     root = insert(root,key);
     break;
   case 2:
     printf("Enter the value to delete from the BST\n");
     scanf("%d",&key);
     delete(root,key);
     break;
   case 3:
     print_inorder(root);
     break;
   case 4:
     print_preorder(root);
     break;
   case 5:
     print_postorder(root);
     break;
   case 6:
     if(tmp)
      printf("Min value in BST is %d\n",tmp->info);
     break;
   case 7:
     tmp = find_max(root);
     if(tmp)
      printf("Max value in BST is %d\n",tmp->info);
     break;
   case 8:
     printf("height of the BST is %d\n",height(root));
     break;
   default:
     return 0;
     break;
  }
  printf("Below are the possible opetaions you can performe in the above created BST\n");
  printf("1. Insert\n2. Delete\n3. In-Order\n4. Pre-Order\n5. Post-Order\n6. Find Minimum\n7. Find Max\n8. height\n other value for exit");
  scanf("%d,&option");
 }
}

Popular Posts