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);
}
}



Related Links :

No comments:

Post a Comment


If you face any Problem in viewing code such as Incomplete "For Loops" or "Incorrect greater than or smaller" than equal to signs then please collect from My Web Site CLICK HERE


More Useful Topics...

 

History Of C..

In the beginning was Charles Babbage and his Analytical Engine, a machine
he built in 1822 that could be programmed to carry out different computations.
Move forward more than 100 years, where the U.S. government in
1942 used concepts from Babbage’s engine to create the ENIAC, the first
modern computer.
Meanwhile, over at the AT&T Bell Labs, in 1972 Dennis Ritchie was working
with two languages: B (for Bell) and BCPL (Basic Combined Programming
Language). Inspired by Pascal, Mr. Ritchie developed the C programming
language.

My 1st Program...


#include
#include
void main ()
{
clrscr ();
printf ("\n\n\n\n");
printf ("\t\t\t*******Pankaj *******\n");
printf ("\t\t\t********************************\n");
printf ("\t\t\t\"Life is Good...\"\n");
printf ("\t\t\t********************************");
getch ();
}

Next Step...


#include
#include

void main ()
{
clrscr ();
printf ("\n\n\n\n\n\n\n\n");
printf ("\t\t\t --------------------------- \n\n");

printf ("\t\t\t | IGCT, Info Computers, INDIA | \n\n");
printf ("\t\t\t --------------------------- ");

getch ();

}

Hits!!!