Implementation of Binary Search Tree using C Programming Language
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
struct node{
int data;
struct node *left;
struct node *right;
}*root=NULL;
void bstinsert(int d,struct node*r){
struct node *temp;
if(r==NULL){
temp=(struct node*)malloc(sizeof(struct node));
temp->data=d;
temp->left=NULL;
temp->right=NULL;
root=temp;
}
else if(d<r->data){
if(r->left==NULL){
struct node *temp=(struct node*)malloc(sizeof(struct node));
temp->data=d;
temp->left=NULL;
temp->right=NULL;
r->left=temp;
}
else
bstinsert(d,r->left);
}
else{
if(r->right==NULL){
struct node *temp=(struct node*)malloc(sizeof(struct node));
temp->data=d;
temp->left=NULL;
temp->right=NULL;
r->right=temp;
}
else
bstinsert(d,r->right);
}
}
void bstinserti(int d){
struct node *temp,*temp1,*p;
temp=(struct node*)malloc(sizeof(struct node));
temp->data=d;
temp->left=NULL;
temp->right=NULL;
if(root==NULL)
root=temp;
else
{
p=NULL;
temp1=root;
while(temp1!=NULL)
{
p=temp1;
if(d<temp1->data)
temp1=temp1->left;
else
temp1=temp1->right;
}
if(d<p->data)
p->left=temp;
else
p->right=temp;
}
}
void inorder(struct node *t){
if(t!=NULL){
inorder(t->left);
printf("%d ",t->data);
inorder(t->right);
}
}
void preorder(struct node *t){
if(t!=NULL){
printf("%d ",t->data);
preorder(t->left);
preorder(t->right);
}
}
void postorder(struct node *t){
if(t!=NULL){
postorder(t->left);
postorder(t->right);
printf("%d ",t->data);
}
}
int count(struct node*t){
if(t==NULL)
return 0;
else
return (1+count(t->left)+count(t->right));}
int suc(int d,struct node*r){
static int p;
if(r!=NULL){
suc(d,r->right);
if(r->data>d)
p=r->data;
suc(d,r->left);
}
return p;
}
int pred(int d,struct node*r){
static int p;
if(r!=NULL){
pred(d,r->left);
if(r->data<d)
p=r->data;
pred(d,r->right);
}
return p;
}
void findsmallest(struct node*t){
if(t->left==NULL)
printf("%d",t->data);
else
findsmallest(t->left);
}
void deletenode(struct node *r,int d){
struct node *temp,*parent,*t;
int s;
parent=NULL;
temp=r;
while(temp->data!=d){
parent=temp;
if(d<temp->data)
temp=temp->left;
else
temp=temp->right;
}
//case1:when temp has no child
if (temp->left==NULL && temp->right==NULL)
{
if(temp==parent->left)
parent->left=NULL;
else
parent->right=NULL;
free(temp);
}
//case2.left temp has 1 child only i.e. left child
else if(temp->left!=NULL && temp->right==NULL){
if(temp==root)
root=temp->left;
if(temp==parent->left)
parent->left=temp->left;
else
parent->right=temp->left;
free(temp);}
//case2.right: temp has 1 child only i.e. right child
else if(temp->left!=NULL && temp->right==NULL){
if(temp==root)
root=temp->right;
if(temp==parent->left)
parent->left=temp->right;
else
parent->right=temp->right;
free(temp);
}
//case3: temp has has both the children;
else{
s=suc(d,root);
deletenode(r,s);
temp->data=s;
}
}
void main(){
int i;
int d[]={15,7,19,12,9,3,17,27};
clrscr();
for(i=0;i<8;i++)
bstinserti(d[i]);
printf("Inorder:");
inorder(root);
getch();
printf("\npre order:");
preorder(root);
getch();
printf("\npost order:");
postorder(root);
getch();
printf("\nSucessor %d",suc(9,root));
getch();
printf("\nPredcessor %d",pred(9,root));
getch();
printf("\nNumber of elements%d",count(root));
getch();
printf("\nSmallest No.");
findsmallest(root) ;
deletenode(root,27);
printf("\nInorder:");
inorder(root);
getch();
}
Comments
Post a Comment