/*
In This
Binary Search Tree
Operations We Do
=> Insert Element
=> Delete Element
=> Find Maximum Element
=> Find Minimum Element
=> Search Element
*/
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#include<math.h>
#include<time.h>
#define Max
20
struct Node
{
int val;
struct Node *lptr;
struct Node *rptr;
};
int
SearchNode(struct Node* n, int x);
struct Node*
InsertIntoTree(struct Node* n, int x);
struct Node*
DeleteFromTree(struct Node* n, int x);
struct Node*
SearchMaxElement(struct Node *n);
struct Node*
SearchMinElement(struct Node *n);
void InOrderTraversal(struct
Node* n);
void
PostOrderTraversal(struct Node* n);
void
PreOrderTraversal(struct Node* n);
void main()
{
struct Node *n=NULL;
struct Node *Min_Max_Value;
int i,j,Temp_Val,Flag=1;
char ch;
float Traverse_Time;
clock_t first,second;
do
{
printf("\nMenu....");
printf("\n1. Insert
Element \n2. Delete Element \n3. Find Maximum \n4. Find Minimum \n5. Search
Element");
printf("\n6. InOrder
Traversal \n7. PreOrder Traversal \n8. Post Order Traversal \n9. Exit");
printf("\nEnter
Choice : ");
scanf("%d",&ch);
clrscr();
switch(ch)
{
case 1: printf("\nEnter Element to be Inserted :
");
scanf("%d",&Temp_Val);
n
= InsertIntoTree(n,Temp_Val);
printf("\nElement
Inserted");
break;
case 2:
first = clock();
printf("\nEnter
Element to be deleted : ");
scanf("%d",&Temp_Val);
n
= DeleteFromTree(n,Temp_Val);
InOrderTraversal(n);
printf("\nElement
Deleted");
second
= clock();
Traverse_Time
= (second-first)/CLOCKS_PER_SEC;
printf("\nTime
To Delete Element is %f",Traverse_Time);
break;
case 3:
first = clock();
Min_Max_Value
= SearchMaxElement(n);
printf("\nMaximum
Element in Tree : %d",Min_Max_Value->val);
second
= clock();
Traverse_Time
= (second-first)/CLOCKS_PER_SEC;
printf("\nTime
To Find Max Element is %f",Traverse_Time);
break;
case 4:
first = clock();
Min_Max_Value
= SearchMinElement(n);
printf("\nMinimum
Element in Tree : %d",Min_Max_Value->val);
second
= clock();
Traverse_Time
= (second-first)/CLOCKS_PER_SEC;
printf("\nTime
To Find Min Element is %f",Traverse_Time);
break;
case 5:
first = clock();
printf("\nEnter
Element to search : ");
scanf("%d",&Temp_Val);
Flag
= SearchNode(n,Temp_Val);
if(Flag!=0)
printf("\nElement
Not Found");
else
printf("\nElement
Found");
second
= clock();
Traverse_Time
= (second-first)/CLOCKS_PER_SEC;
printf("\nTime
To Search Element is %f",Traverse_Time);
break;
case 6:
first = clock();
printf("\nIn
Order Traversal...");
InOrderTraversal(n);
second
= clock();
Traverse_Time
= (second-first)/CLOCKS_PER_SEC;
printf("\nTime
To InOrder Traversal is %f",Traverse_Time);
break;
case 7:
first = clock();
printf("\nPre
Order Traversal...");
PreOrderTraversal(n);
second
= clock();
Traverse_Time
= (second-first)/CLOCKS_PER_SEC;
printf("\nTime
To PreOrder Traversal is %f",Traverse_Time);
break;
case 8:
first = clock();
printf("\nPost
Order Traversal...");
PostOrderTraversal(n);
second
= clock();
Traverse_Time
= (second-first)/CLOCKS_PER_SEC;
printf("\nTime
To PostOrder Traversal is %f",Traverse_Time);
break;
default:
exit(0);
}
printf("\nDo You
want to Continue [y/n]...");
}while(getchar()=='Y' || getchar()=='y');
getch();
}
int
SearchNode(struct Node *n, int x)
{
if (n->val==x)
return 0;
else if(n->lptr==NULL &&
n->rptr==NULL)
return 1;
else if(x < n->val)
return
SearchNode(n->lptr,x);
else if(x > n->val)
return
SearchNode(n->rptr,x);
}
struct Node
*InsertIntoTree(struct Node *n, int x)
{
struct Node *newNode;
newNode = (struct
Node*)malloc(sizeof(struct Node));
newNode->val = x;
newNode->lptr = newNode->rptr =
NULL;
if(n==NULL)
{
n = newNode;
n->lptr=NULL;
n->rptr=NULL;
}
else
{
if(x < n->val)
n->lptr
= InsertIntoTree(n->lptr,x);
else
n->rptr
= InsertIntoTree(n->rptr,x);
}
return n;
}
struct Node
*DeleteFromTree(struct Node *n, int x)
{
if(n==NULL)
printf("\nNo any
element exist in Tree");
else if(x < n->val)
n->lptr =
DeleteFromTree(n->lptr,x);
else if(x > n->val)
n->rptr =
DeleteFromTree(n->rptr,x);
else
{
if(n->lptr !=NULL
&& n->rptr != NULL)
{
struct
Node *Max_Ele;
Max_Ele =
SearchMaxElement(n->lptr);
n->val
= Max_Ele->val;
n->lptr
= DeleteFromTree(n->lptr,Max_Ele->val);
}
else
{
struct
Node *Temp;
Temp = n;
if(n->lptr
== NULL)
n
= n->rptr;
else
n
= n->lptr;
free(Temp);
}
}
return (n);
}
struct Node
*SearchMaxElement(struct Node *n)
{
if (n==NULL || n->rptr == NULL)
return n;
else
return
SearchMaxElement(n->rptr);
}
struct Node
*SearchMinElement(struct Node *n)
{
if(n==NULL || n->lptr == NULL)
return n;
else
return SearchMinElement(n->lptr);
}
void
InOrderTraversal(struct Node *n)
{
struct Node *Cur, *Pre;
if(n==NULL)
return;
Cur = n;
while(Cur != NULL)
{
if(Cur->lptr == NULL)
{
printf("\t%d",Cur->val);
Cur=
Cur->rptr;
}
else
{
Pre =
Cur->lptr;
while(Pre->rptr
!=NULL && Pre->rptr != Cur)
Pre
= Pre->rptr;
if
(Pre->rptr == NULL)
{
Pre->rptr
= Cur;
Cur
= Cur->lptr;
}
else
{
Pre->rptr
= NULL;
printf("\t%d",Cur->val);
Cur
= Cur->rptr;
}
}
}
}
void PreOrderTraversal(struct
Node* n)
{
if(n!=NULL)
{
printf("\t%d",n->val);
PreOrderTraversal(n->lptr);
PreOrderTraversal(n->rptr);
}
}
void
PostOrderTraversal(struct Node *n)
{
if(n!=NULL)
{
PostOrderTraversal(n->lptr);
PostOrderTraversal(n->rptr);
printf("\t%d",n->val);
}
}
