If Screen is half, please rotate the Mobile then it is full program available
10. Design, Develop and Implement a menu driven Program in C for the following operations on Binary Search Tree (BST) of Integers
a. Create a BST of N Integers: 6, 9, 5, 2, 8, 15, 24, 14, 7, 8, 5, 2
b. Traverse the BST in Inorder, Preorder and Post Order
c. Search the BST for a given element (KEY) and report the appropriate message
e. Exit
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
typedef struct TreeData
{
int key;
}Record;
typedef struct Node *ListPointer;
typedef struct Node
{
ListPointer lLink;
Record data;
ListPointer rLink;
}Node;
ListPointer tree;
Record getNextRecord ( void )
{
Record data;
scanf ( "%d", &data.key );
return data;
}
ListPointer getNode ( Record data )
{
ListPointer temp;
temp = ( ListPointer ) malloc ( sizeof ( *temp ) );
if ( temp == NULL )
{
printf ( "\n\n Allocation Failed\n\n" );
getchar (); //getch();
exit ( EXIT_FAILURE );
}
else
{
temp->data = data;
temp->lLink = temp->rLink = NULL;
}
return temp;
}
void inorder ( ListPointer tree )
{
if ( tree )
{
inorder ( tree->lLink );
printf ( "%d\t", tree->data.key );
inorder ( tree->rLink );
}
}
void preorder ( ListPointer tree )
{
if ( tree )
{
printf ( "%d\t", tree->data.key );
preorder ( tree->lLink );
preorder ( tree->rLink );
}
}
void postorder ( ListPointer tree )
{
if ( tree )
{
postorder ( tree->lLink );
postorder ( tree->rLink );
printf ( "%d\t", tree->data.key );
}
}
int search ( ListPointer tree, Record data )
{
while ( tree )
{
if ( data.key == tree->data.key )
{
return 1;
}
if ( data.key < tree->data.key )
{
tree = tree->lLink;
}
else
{
tree = tree->rLink;
}
}
return 0;
}
ListPointer modifiedSearch ( ListPointer tree, Record data )
{
ListPointer parent = NULL;
while ( tree )
{
parent = tree;
if ( data.key == tree->data.key )
{
return NULL;
}
if ( data.key < tree->data.key )
{
tree = tree->lLink;
}
else
{
tree = tree->rLink;
}
}
return parent;
}
void insert ( Record data )
{
ListPointer ptr, temp = modifiedSearch ( tree, data);
if ( temp || !tree )
{
ptr = getNode( data );
if ( tree )
{
if ( data.key < temp->data.key )
{
temp->lLink = ptr;
}
else
{
temp->rLink = ptr;
}
}
else
{
tree = ptr;
}
}
}
int main ( void )
{
Record data;
int nRecords;
int choice;
int i;
printf("\n.. BINARY SEARCH TREE DEMONSTRATION ..\n");
printf ( "\n\n1. Insert\n");
printf ( "\n2. Inoreder \t3. Preorder \t4. Postorder\n");
printf ( "\n5. Search for an Item\n");
printf ( "\n6. Exit\n");
while ( 1 )
{
printf ( "\nChoice: " );
scanf ( "%d", &choice );
switch ( choice )
{
case 1: printf("\n.. * INSERTION ..\n");
printf ( "\nHow many RECORDS: " );
scanf ( "%d", &nRecords );
printf("\nGive %d record details one by one\n", nRecords);
for ( i = 0; i < nRecords; ++ i )
{
data = getNextRecord();
insert ( data );
}
break;
case 2: if ( tree )
{
printf ( "\n\n Inorder Traversal\n\n" );
inorder ( tree );
}
else printf ( "\n\nBST is Empty\n\n" );
break;
case 3: if ( tree )
{
printf ( "\n\nPreorder Traversal\n\n" );
preorder ( tree );
}
else
{
printf ( "\n\nBST is Empty\n\n" );
}
break;
case 4: if ( tree )
{
printf ( "\n\n Postorder Traversal\n\n" );
postorder ( tree );
}
else
{
printf ( "\n\nBST is Empty\n\n" );
}
break;
case 5: if ( tree )
{
printf ( "\n\nSearch for an Item: ?\n" );
data = getNextRecord();
if ( search ( tree, data ) )
{
printf ( "\n\n Item is Present is BST\n\n" );
}
else
{
printf ( "\n\n Item is not present in BST\n\n" );
}
}
break;
case 6: return 0;
default: printf ( "\nWrong Choice\n" );
}
}
}
OUTPUT:
.. BINARY SEARCH TREE DEMONSTRATION ..
1. Insert
2. Inoreder 3. Preorder 4.Postorder
5. Search for an Item
6. Exit
Choice: 1
.. * INSERTION ..
How many RECORDS: 12
Give 12 record details one by one
6
9
5
2
8
15
24
14
7
8
5
2
Choice: 2
Inorder Traversal
2 5 6 7 8 9 14 15 24
Choice: 3
Preorder Traversal
6 5 2 9 8 7 15 14 24
Choice: 4
Postorder Traversal
2 5 7 8 14 24 15 9 6
Choice: 5
Search for an Item: ?
14
Item is Present is BST
Choice: 5
Search for an Item: ?
10
Item is not present in BST
Choice: 6 Exit