C Tutor... C Tutorial....: C Program to insert and delete a node from the binary search tree

C Program to insert and delete a node from the binary search tree

#include
#include
#include
#define TRUE 1
#define FALSE 0
struct btreenode
{
  struct btreenode *leftchild;
  int data;
  struct btreenode *rightchild;
};
void insert(struct btreenode **,int);
void del(struct btreenode **,int);
void search(struct btreenode **,int,struct btreenode **,struct btreenode **,int *);
void inorder(struct btreenode *);
void main()
{
  struct btreenode *bt;
  int req;
  int i=0,num,a[]={10,7,11,5,8,12,16,15,6};
  bt=NULL; /* Empty Tree */
  clrscr();
  while(i<=8)    {       insert(&bt,a[i]);       i++;    }    clrscr();    printf(" Binary tree before deletion :\n");    inorder(bt);    del(&bt,11);    printf("\n Binary tree after deletion :\n");    inorder(bt);    del(&bt,10);    printf("\n Binary tree after deletion :\n");    inorder(bt);    del(&bt,6);    printf("\n Binary tree after deletion :\n");    inorder(bt);    del(&bt,16);    printf("\n Binary tree after deletion :\n");    inorder(bt);    getch(); } /* inserts a new node in a binary search tree */ void insert(struct btreenode **sr,int num) {    if(*sr==NULL)    {       (*sr)=malloc(sizeof(struct btreenode));       (*sr)->leftchild=NULL;
     (*sr)->data=num;
     (*sr)->rightchild=NULL;
  }
  else   /* Search the node to whilch new node will be attatched */
  {
      /* If new data is less, traverse to left*/
      if(num<(*sr)->data)
  insert(&((*sr)->leftchild),num);
      else
  /* Else traverse to right */
  insert(&((*sr)->rightchild),num);
  }
}
/* Deletes a node from the binary search tree */
void del(struct btreenode **root,int num)
{
  int found;
  struct btreenode *parent,*x,*xsucc;
  /* If tree is empty */
  if(*root == NULL)
  {
      printf("\n Tree is Empty ");
      return;
  }
  parent=x=NULL;
  /* Call to search function to find the node to be deleted */
  search(root,num,&parent,&x,&found);
  /* If the node to be deleted is not found */
  if(found == FALSE)
  {
    printf("\n Data to be deleted , not found ");
    return;
  }
  /* If the node to be deleted has two children */
  if(x->leftchild !=NULL && x->rightchild!=NULL)
  {
    parent=x;
    xsucc=x->rightchild;
    while(xsucc->leftchild != NULL)
    {
      parent=xsucc;
      xsucc=xsucc->leftchild;
    }
    x->data=xsucc->data;
    x=xsucc;
  }
  /* If the node to be deleted has no child */
  if(x->leftchild==NULL && x->rightchild==NULL)
  {
    if(parent->rightchild==x)
parent->rightchild=NULL;
    else
parent->rightchild=NULL;
    free(x);
    return;
  }
  /* If the node to be deleted has only right child */
  if(x->leftchild==NULL && x->rightchild !=NULL)
  {
    if(parent->leftchild==x)
      parent->leftchild=x->rightchild;
    else
      parent->rightchild=x->rightchild;
    free(x);
    return;
  }
  /* If the node to be deleted has only left child */
  if(x->leftchild != NULL && x->rightchild==NULL)
  {
    if(parent->leftchild==x)
      parent->leftchild=x->leftchild;
    else
      parent->rightchild=x->rightchild;
    free(x);
    return;
  }
}

/* Returns the address of the node to be deleted ,address of its parent and whether the node is found or not */
void search(struct btreenode **root,int num,struct btreenode **par,struct btreenode **x,int *found)
{
 struct btreenode *q;
 q=*root;
 *found=FALSE;
 *par=NULL;
 while(q!=NULL)
 {
    /* If the node to be deleted is found */
    if(q->data == num)
    {
      *found=TRUE;
      *x=q;
      return;
    }
    if(q->data==num)
    {
      *found=TRUE;
      *x=q;
      return;
    }
    *par=q;
    if(q->data > num)
q=q->leftchild;
    else
q=q->rightchild;
 }
}
/* Traverse a binary search tree in an LDR(Left-Data-Right) fashion */
void inorder(struct btreenode *sr)
{
  if(sr!=NULL)
  {
     inorder(sr->leftchild);
  /* Print the data of the node whose leftchild is NULL or the path has already been traversed */
  printf("%d\t",sr->data);
  inorder(sr->rightchild);
  }
}