# SEARCH TREE ADT - BINARY SEARCH TREE

SOURCE CODE:

“Tree.h” File:

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
struct node
{
int data;
struct node *left;
struct node *right;
};
typedef struct node *ptrToNode;
typedef ptrToNode TREE;
typedef ptrToNode POSITION;

POSITION createnode(int x)
{
POSITION P;
P=(struct node*)malloc(sizeof(struct node));
if(P==NULL)
printf("\n\n FATAL ERROR");
else
{
P->data=x;
P->left=P->right=NULL;
}
return P;
}
void MakeEmpty(TREE T)
{
if(T!=NULL)
{
MakeEmpty(T->left);
MakeEmpty(T->right);
free(T);
}
}
TREE Insert(int x,TREE T)
{
if(T==NULL)
T=createnode(x);
else if(x<T->data)
T->left=Insert(x,T->left);
else if(x>T->data)
T->right=Insert(x,T->right);
else
printf("\n Element is already present in the tree");
return T;
}

POSITION Find(int x,TREE T)
{
if(T==NULL)
return NULL;
else if(x<T->data)
return Find(x,T->left);
else if(x>T->data)
return Find(x,T->right);
else
return T;
}
POSITION Findmin(TREE T)
{
if(T==NULL)
return NULL;
else if(T->left==NULL)
return T;
else
return Findmin(T->left);
}
POSITION Findmax(TREE T)
{
if(T==NULL)
return NULL;
else if(T->right==NULL)
return T;
else
return Findmax(T->right);
}
TREE Delete(int x,TREE T)
{
POSITION temp;
if(T==NULL)
else if(x<T->data)
T->left=Delete(x,T->left);
else if(x>T->data)
T->right=Delete(x,T->right);
else if(T->left&&T->right)
{
temp=Findmin(T->right);
T->data=temp->data;
T->right=Delete(T->data,T->right);
}
else
{
temp=T;
if(T->left==NULL)
T=T->right;
else if(T->right==NULL)
T=T->left;
free(temp);

}
return T;
}
void Display(TREE T)
{
if(T!=NULL)
{
Display(T->left);
printf("\n%d",T->data);
Display(T->right);
}
}

“Tree.c” File:

#include"tree.h"
void main()
{
TREE T=NULL;
POSITION P=NULL;
int ch,x;
clrscr();
printf("\n1.create \n2.Insert \n3.Delete \n4.MakeEmpty \n5.Find \n6.Findmin \n7.Findmax \n8.Display \n9.Exit");
A:
printf("\n Enter Ur choice:\t");
scanf("%d",&ch);
switch(ch)
{
case 1:
if(T==NULL)
{
printf("\n Enter the Element:\t");
scanf("%d",&x);
T=createnode(x);
}
break;
case 2:
if(T==NULL)
printf("\n Tree is not yet created");
else
{
printf("\n Enter the element to insert:\t");
scanf("%d",&x);
T=Insert(x,T);
}
break;
case 3:
if(T==NULL)
printf("\n Tree is not yet created");
else
{

printf("\n Enter the element to delete:\t");
scanf("%d",&x);
T=Delete(x,T);
}
break;
case 4:
if(T==NULL)
printf("\n Tree is not yet created");
else
{
MakeEmpty(T);
T=NULL;
printf("\n Tree is empty now");
}
break;
case 5:
if(T==NULL)
printf("\n Tree is not yet created");
else
{
printf("\n Enter the element to find");
scanf("%d",&x);
P=Find(x,T);
if(P==NULL)
else
printf("\n Element is found in the tree");
}
break;
case 6:
if(T==NULL)
printf("\n Tree is not yet created");
else
{
P=Findmin(T);
printf("\n Minimun element in the Tree is %d",P->data);
}
break;
case 7:
if(T==NULL)
printf("\n Tree is not yet created");
else
{
P=Findmax(T);
printf("\n Maximum element in the Tree is %d",P->data);
}
break;
case 8:
if(T==NULL)
printf("\n Tree is not yet created");
else
Display(T);
break;
case 9:
exit(0);
default:
printf("\n Ur Option is Wrong");
}
goto A;
}

OUTPUT:

1.create
2.Insert
3.Delete
4.MakeEmpty
5.Find
6.Findmin
7.Findmax
8.Display
9.Exit
Enter Ur choice:       1
Enter the Element:     20

Enter Ur choice:       2
Enter the element to insert:   15

Enter Ur choice:       2
Enter the element to insert:   30

Enter Ur choice:       2
Enter the element to insert:   10

Enter Ur choice:       2
Enter the element to insert:   25

Enter Ur choice:       2
Enter the element to insert:   40

Enter Ur choice:       2
Enter the element to insert:   35

Enter Ur choice:       2
Enter the element to insert:   31

Enter Ur choice:       8
10
15
20
25
30
31
35
40

Enter Ur choice:       5
Enter the element to find30
Element is found in the tree

Enter Ur choice:       6
Minimun element in the Tree is 10

Enter Ur choice:       7
Maximum element in the Tree is 40

Enter Ur choice:       3
Enter the element to delete:   20

Enter Ur choice:       8
10
15
25
30
31
35
40

Enter Ur choice:       3
Enter the element to delete:   40

Enter Ur choice:       8
10
15
25
30
31
35

Enter Ur choice:       7
Maximum element in the Tree is 35

Enter Ur choice:       4
Now Tree becomes Empty

Enter Ur choice:       2
Tree is not yet created

Enter Ur choice:       9
Previous
Next Post »