BINARY SEARCH TREE in C....

All Operations in BST......

   
 #include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
typedef struct btree
{
 struct btree *left ;
 int data ;
 struct btree *right ;
}tree;
void insert ( tree **, int ) ;
void del ( tree **, int ) ;
void search ( tree **,int,tree **, tree **, int *);
void inorder ( tree * );
int main( )
{
 tree *bt ;
 int i,num;
 bt = NULL ;  /* empty tree */
    while(1)
    {
 printf("1. Insert");
 printf("\n2. Delete");
 printf("\n3. Show");
 printf("\n4. Exit");
 printf("\nEnter your choice: ");
 scanf("%d",&i);
 switch(i)
 {
     case 1:
  printf("Enter no to insert: ");
  scanf("%d",&num);
  insert(&bt,num);
  break;
     case 2:
  printf("Enter no to insert: ");
  scanf("%d",&num);
  del(&bt,num);
  break;
     case 3:
  inorder(bt);
  getch();
  break;
     case 4:
  exit(0);
  break;
 }
    }
    return 0;
}
void insert ( tree **sr, int num )
{
 if ( *sr == NULL )
 {
  (*sr)= (tree *)malloc (sizeof(tree)) ;
  ( *sr ) -> left = NULL ;
  ( *sr ) -> data = num ;
  ( *sr ) -> right = NULL ;
 }
 else  /* search the node to which new node will be attached */
 {
  /* if new data is less, traverse to left */
  if ( num < ( *sr ) -> data )
   insert ( &( ( *sr ) -> left ), num ) ;
  else
   /* else traverse to right */
   insert ( &( ( *sr ) -> right ), num ) ;
 }
}
void del ( tree **root, int num )
{
 int found ;
 tree *parent, *x, *xsucc ;
 if ( *root == NULL )
 {
  printf ( "\nTree is empty" ) ;
  return ;
 }
 parent = x = NULL ;
 /* call to search function to find the node to be deleted */
 search ( root, num, &parent, &x, &found ) ;
 if ( found == FALSE )
 {
  printf ( "\nData to be deleted, not found" ) ;
  return ;
 }
 /* if the node to be deleted has two children */
 if ( x -> left != NULL && x -> right != NULL )
 {
  parent = x ;
  xsucc = x -> right ;
  while ( xsucc -> left != NULL )
  {
   parent = xsucc ;
   xsucc = xsucc -> left ;
  }
  x -> data = xsucc -> data ;
  x = xsucc ;
 }
 /* if the node to be deleted has no child */
 if ( x -> left == NULL && x -> right == NULL )
 {
  if ( parent -> right == x )
   parent -> right = NULL ;
  else
   parent -> left = NULL ;
  free ( x ) ;
  return ;
 }
 /* if the node to be deleted has only right */
 if ( x -> left == NULL && x -> right != NULL )
 {
  if ( parent -> left == x )
   parent -> left = x -> right ;
  else
   parent -> right = x -> right ;
  free ( x ) ;
  return ;
 }
 /* if the node to be deleted has only left child */
 if ( x -> left != NULL && x -> right == NULL )
 {
  if ( parent -> left == x )
   parent -> left = x -> left ;
  else
   parent -> right = x -> left ;
  free ( x ) ;
  return ;
 }
}
void search ( tree **root, int num, tree **par, tree **x, int *found )
{
 tree *q ;
 q = *root ;
 *found = FALSE ;
 *par = NULL ;
 while ( q != NULL )
 {
  if ( q -> data == num )
  {
   *found = TRUE ;
   *x = q ;
   return ;
  }
  *par = q ;
  if ( q -> data > num )
   q = q -> left ;
  else
   q = q -> right ;
 }
}
void inorder ( tree *sr )
{
 if ( sr != NULL )
 {
  inorder ( sr -> left ) ;
  printf ( "%d\t", sr -> data ) ;
  inorder ( sr -> right ) ;
 }
}