|
C Program To Implement Binary Search Tree Using Abstract Data Type: |
|
#include
#include
#include
#include
struct tree
{
int data;
struct tree *lchild;
struct tree *rchild;
}
*t, *temp;
int element;
void inorder (struct tree*);
struct tree *create (struct tree*, int);
struct tree *find (struct tree*, int);
struct tree *insert (struct tree*, int);
struct tree *del (struct tree*, int);
struct tree *findmin (struct tree*);
struct tree *findmax (struct tree*);
void main( )
{
int ch;
printf (“\n\n\t BINARY SEARCH TREE”);
do
{
printf (“\nMain Menu\n”);
printf (“\n1.Create \n2.Insert \n3.Delete \n4.Find \n5.Findmax \n6.Findmin”);
printf (“\n7.Exit”);
printf (“\nEnter your choice:”);
scanf (“%d”, &ch);
switch(ch)
{
case 1:
printf (“Enter the element\n”);
scanf (“%d”, &element);
t = create (t, element);
inorder(t);
break;
case 2:
printf (“Enter the element\n”);
scanf (“%d”, &element);
t = insert (t, element);
inorder(t);
break;
case 3:
printf (“Enter the data”);
scanf (“%d”, &element);
t = del (t, element);
inorder(t);
break;
case 4:
printf (“Enter the data”);
scanf (“%d”, &element);
temp = find (t, element);
if(temp?data = = element)
printf (“Element %d is found”, element);
else
printf (“Element is not found”);
break;
case 5:
temp = findmax(t);
printf(“Maximum element is %d”, temp?data);
break;
case 6:
temp = findmin(t);
printf (“Minimum element is %d”, temp?data);
break;
}
}
while(ch != 7)
}
struct tree *create (struct tree* t, int element)
{
t = (struct tree*) malloc (sizeof(struct tree));
t?(struct tree*)malloc(sizeof (struct tree) );
t?data = element;
t? lchild = NULL;
t? rchild = NULL;
return t;
}
struct tree *find (struct tree* t, int element)
{
if ( t= = NULL)
return NULL;
if (element< t?data)
return (find(t?rchild, element) );
else
return t;
}
struct tree *findmin (struct tree* t)
{
if ( t = = NULL)
return NULL;
else
if (t?lchild = = NULL)
return t;
else
return (findmin (t?lchild));
}
struct tree *findmax (struct tree* t)
{
if (t! = NULL)
{
while (t?rchild ! = NULL)
t = t?rchild;
}
return t;
}
struct tree *insert (struct tree* t, int element)
{
if (t= = NULL)
{
t = (struct tree*) malloc (sizeof(struct tree));
t?data = element;
t?lchild = NULL;
t?rchild = NULL;
return t;
}
else
{
if(element< t?data)
{
t?lchild = insert(t?lchild, element);
}
else
if (element> t?data)
{
t?rchild = insert (t?rchild, element);
}
else
if(element = = t?data)
{
printf ( “Element already present\n”);
}
return t;
}}
struct tree* del (struct tree* t, int element)
{
if (t = = NULL)
printf (“Element not found\n”);
else
if(element< t?data)
t?lchild = del (t?lchild, element);
else
if(element> t?data)
t?rchild = del (t?rchild, element);
else
if(t?lchild && t?rchild);
{
temp = findmin (t?rchild);
{
t?data = temp?data;
t?rchild = del (t?rchild, t?data);
}
else
{
temp = t;
if (t?lchild = = NULL)
t = t?rchild;
else
if (t?rchild = = NULL)
t = t?lchild;
free (temp);
}
return t;
}
void inorder (struct tree *t)
{
if (t = = NULL)
return;
else
{
inorder (t?lchild);
printf (“\t%d”, t?data);
inorder (t?rchild);
}
}
SAMPLE INPUT AND OUTPUT:
Main Menu
1.Create
2.Insert
3.Delete
4.Find
5.Findmax
6.Findmin
7.Exit
Enter your choice: 1
Enter the element
12
12
Main Menu
1.Create
2.Insert
3.Delete
4.Find
5.Findmax
6.Findmin
7.Exit
Enter your choice: 2
Enter the element
13
12 13
Main Menu
1.Create
2.Insert
3.Delete
4.Find
5.Findmax
6.Findmin
7.Exit
Enter your choice: 3
Enter the data12
13
Main Menu
1.Create
2.Insert
3.Delete
4.Find
5.Findmax
6.Findmin
7.Exit
Enter your choice: 4
Enter the data13
Element 13 is found
Main Menu
1.Create
2.Insert
3.Delete
4.Find
5.Findmax
6.Findmin
7.Exit
Enter your choice: 2
Enter the element
14
13 14
Main Menu
1.Create
2.Insert
3.Delete
4.Find
5.Findmax
6.Findmin
7.Exit
Enter your choice: 2
Enter the element
15
13 14 15
Main Menu
1.Create
2.Insert
3.Delete
4.Find
5.Findmax
6.Findmin
7.Exit
Enter your choice: 5
Maximum element is 15
Main Menu
1.Create
2.Insert
3.Delete
4.Find
5.Findmax
6.Findmin
7.Exit
Enter your choice: 6
Minimum element is 13
Main Menu
1.Create
2.Insert
3.Delete
4.Find
5.Findmax
6.Findmin
7.Exit
Enter your choice: 7
|
|
⇓ Student Projects ⇓
⇑ Student Projects ⇑ |