Data Structure program on Binary Search trees BST.

Implement Add, Traversals (Pre-order, In-order, Post-order) and Search operations on BST – Binary Search trees.

/* Binary Search Tree - Recursive Program */

#include
#include
#include
#include

struct bs_tr
{
char data[4];
struct bs_tr *left;
struct bs_tr *right;
};
struct bs_tr *root = NULL;
int n_count = 0;
int found = 0;
void add(struct bs_tr *, struct bs_tr *);
void srch(struct bs_tr *, char[]);
void dis_pre(struct bs_tr *);
void dis_in(struct bs_tr *);
void dis_post(struct bs_tr *);

void main()
{
int choice = 1;
char value[4];
struct bs_tr *new_ptr;
while (choice != 7)
{
clrscr();
printf("Binary Search Tree Operations (Recursive) :-\n");
printf("------ ------ ---- ---------- -----------\n\n");
printf("1] Add a new node\n");
printf("2] Delete a node\n");
printf("3] Search the BST\n");
printf("4] Display - preorder\n");
printf("5] Display - inorder\n");
printf("6] Display - postorder\n");
printf("7] Exit\n\n");
printf("Enter your choice :- ");
scanf("%d",&choice);
switch (choice)
{
case 1 :
new_ptr = (struct bs_tr *) malloc(sizeof(struct bs_tr));
if (new_ptr == NULL)
{
printf("\nMemory Full...Cannot add...");
getch();
break;
}
new_ptr->left = NULL;
new_ptr->right = NULL;
printf("\n\nEnter the node's data item :- ");
flushall();
scanf("%s",&value);
strcpy(new_ptr->data,value);
n_count = n_count + 1;
if (root == NULL)
{
root = new_ptr;
}
else
{
add(root, new_ptr);
}
break;
case 2 :
if (root == NULL)
{
printf("\n\nTree empty...cannot delete...\n");
getch();
}
else
{
clrscr();
printf("Delete program for recursive approach is not coded...\n\n");
getch();
}
break;
case 3 :
if (root == NULL)
{
printf("\n\nTree empty...cannot search...\n");
getch();
}
else
{
clrscr();
printf("\n\nEnter data item to search for :- ");
flushall();
scanf("%s",&value);
found = 0;
srch(root, value);
if (found == 0)
{
printf("\n\nData does not exist in the BST...Unsuccessful Search...");
getch();
}
else
{
clrscr();
printf("Search Opeartion :-\n");
printf("------ ---------\n\n");
printf("Root = %d\n", root);
printf("Total No of nodes in the BST = %d\n",n_count);
printf("Search for data = %s\n\n", value);
printf("\n\nData exists in the BST...Successful Search...");
getch();
}
}
break;
case 4 :
if (root == NULL)
{
printf("\n\nTree empty...can not display...\n");
getch();
}
else
{
clrscr();
printf("Display - Preorder :-\n");
printf("------- --------\n\n");
printf("Root = %d\n", root);
printf("Total No of nodes in the BST = %d\n\n",n_count);
printf("Data Address Left Link Right Link\n");
printf("---- ------- --------- ----------\n");
dis_pre(root);
getch();
}
break;
case 5 :
if (root == NULL)
{
printf("\n\nTree empty...can not display...\n");
getch();
}
else
{
clrscr();
printf("Display - Inorder :-\n");
printf("------- -------\n\n");
printf("Root = %d\n", root);
printf("Total No of nodes in the BST = %d\n\n",n_count);
printf("Data Address Left Link Right Link\n");
printf("---- ------- --------- ----------\n");
dis_in(root);
getch();
}
break;
case 6 :
if (root == NULL)
{
printf("\n\nTree empty...can not display...\n");
getch();
}
else
{
clrscr();
printf("Display - Postorder :-\n");
printf("------- ---------\n\n");
printf("Root = %d\n", root);
printf("Total No of nodes in the BST = %d\n\n",n_count);
printf("Data Address Left Link Right Link\n");
printf("---- ------- --------- ----------\n");
dis_post(root);
getch();
}
break;
case 7 :
break;
default :
printf("\nOut of range\n\n");
choice = 1;
getch();
}
}
clrscr();
printf("\nProgram finished...bye...bye...");
getch();
}

/* Function to add a node to the BST */
void add(struct bs_tr *c_p, struct bs_tr *n_p)
{
if ((c_p->left == NULL) && (strcmp(n_p->data,c_p->data)<=0))
{
c_p->left = n_p;
}
else if ((c_p->left != NULL) && (strcmp(n_p->data,c_p->data)<=0))
{
add(c_p->left, n_p);
}
if ((c_p->right == NULL) && (strcmp(n_p->data,c_p->data)>0))
{
c_p->right = n_p;
}
else if ((c_p->right != NULL) && (strcmp(n_p->data,c_p->data)>0))
{
add(c_p->right, n_p);
}
return;
}

/* Function to search for a specified value in the BST */
void srch(struct bs_tr *c_p, char s_item[])
{
if ((c_p != NULL) && (strcmp(s_item,c_p->data) == 0))
{
found = 1;
}
if ((c_p != NULL) && (strcmp(s_item,c_p->data) < 0))
{
srch(c_p->left, s_item);
}
if ((c_p != NULL) && (strcmp(s_item,c_p->data) > 0))
{
srch(c_p->right, s_item);
}
return;
}

/* Function to display all the nodes of the BST, pre-order*/
void dis_pre(struct bs_tr *c_p)
{
if (c_p != NULL)
{
printf(" %-3s %5d %5d %5d\n",c_p->data,c_p,c_p->left,c_p->right);
dis_pre(c_p->left);
dis_pre(c_p->right);
}
return;
}

/* Function to display all the nodes of the BST, in-order */
void dis_in(struct bs_tr *c_p)
{
if (c_p != NULL)
{
dis_in(c_p->left);
printf(" %-3s %5d %5d %5d\n",c_p->data,c_p,c_p->left,c_p->right);
dis_in(c_p->right);
}
return;
}

/* Function to display all the nodes of the BST, post-order */
void dis_post(struct bs_tr *c_p)
{
if (c_p != NULL)
{
dis_post(c_p->left);
dis_post(c_p->right);
printf(" %-3s %5d %5d %5d\n",c_p->data,c_p,c_p->left,c_p->right);
}
return;
}