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);
}
}
Related Links :
