Data Structure Program - BST Non-recursive Program

/* Binary Search Tree - Non-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(void);
void srch(void);
void del(void);
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(NonRecursive):\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 :
add();
break;
case 2 :
if (root == NULL)
{
printf("\n\nTree empty...can not delete...\n");
getch();
}
else
{
del();
}
break;
case 3 :
if (root == NULL)
{
printf("\n\nTree empty...can not search...\n");
getch();
}
else
{
srch();
}
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_count);
printf("Size of each node in bytes = %d\n\n",sizeof(struct bs_tr));
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_count);
printf("Size of each node in bytes = %d\n\n",sizeof(struct bs_tr));
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_count);
printf("Size of each node in bytes = %d\n\n",sizeof(struct bs_tr));
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(void)
{
char value[4];
struct bs_tr *new_ptr;
struct bs_tr *cur_ptr;
struct bs_tr *prv_ptr;
new_ptr = (struct bs_tr *) malloc(sizeof(struct bs_tr));
if (new_ptr == NULL)
{
printf("\nMemory Full...Can not add...");
getch();
return;
}
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
{
cur_ptr = root;
prv_ptr = NULL;
while (cur_ptr != NULL)
{
prv_ptr = cur_ptr;
if (strcmp(value,cur_ptr->data)<=0)
cur_ptr = cur_ptr->left;
else
cur_ptr = cur_ptr->right;
}
if (strcmp(value,prv_ptr->data)<=0)
prv_ptr->left = new_ptr;
else
prv_ptr->right = new_ptr;
}
return;
}

/* Function to delete a specified value in the BST */
void del(void)
{
char d_item[4];
struct bs_tr *find_ptr = NULL;
struct bs_tr *hold_ptr = NULL;
struct bs_tr *follow_ptr = NULL;
found = 0;
clrscr();
printf("\n\nEnter data item to delete from BST :- ");
flushall();
scanf("%s", &d_item);
find_ptr = root;
while ((find_ptr != NULL) && (found == 0))
{
if (strcmp(d_item,find_ptr->data) == 0)
{
found = 1;
}
if (strcmp(d_item,find_ptr->data) < 0)
{
find_ptr = find_ptr->left;
}
if (strcmp(d_item,find_ptr->data) > 0)
{
find_ptr = find_ptr->right;
}
}
if (found == 0)
{
printf("\n\nData does not exist in the BST...Can not delete...");
getch();
return;
}
clrscr();
printf("Before Delete Opeartion :-\n");
printf("------ ------ ---------\n\n");
printf("Root = %d\n", root);
printf("Total No of nodes in the BST = %d\n",n_count);
printf("Size of each node in bytes = %d\n",sizeof(struct bs_tr));
printf("Search for data = %s\n\n", d_item);
printf("\n\nData exists in the BST...Successful Search...");
getch();
printf("\n\nProceeding to delete...\n\n");
getch();
follow_ptr = NULL;
hold_ptr = NULL;
find_ptr = root;
if (strcmp(d_item,find_ptr->data) == 0)
{
hold_ptr = root->right;
if (hold_ptr == NULL)
{
root = root->left;
}
else
{
root = hold_ptr;
while (hold_ptr->left != NULL)
hold_ptr = hold_ptr->left;
hold_ptr->left = find_ptr->left;
}
}
else
{
found = 0;
while (found == 0)
{
if (strcmp(d_item,find_ptr->data) == 0)
{
found = 1;
continue;
}
follow_ptr = find_ptr;
if (strcmp(d_item,find_ptr->data) < 0)
{
find_ptr = find_ptr->left;
}
if (strcmp(d_item,find_ptr->data) > 0)
{
find_ptr = find_ptr->right;
}
}
hold_ptr = find_ptr->right;
if (hold_ptr == NULL)
{
if (follow_ptr->right == find_ptr)
{
follow_ptr->right = find_ptr->left;
}
else
{
follow_ptr->left = find_ptr->left;
}
}
else
{
if (follow_ptr->right == find_ptr)
{
follow_ptr->right = hold_ptr;
}
else
{
follow_ptr->left = hold_ptr;
}
while (hold_ptr->left != NULL)
{
hold_ptr = hold_ptr->left;
}
hold_ptr->left = find_ptr->left;
}
}
return;
}

/* Function to search for a specified value in the BST */
void srch(void)
{
char s_item[4];
struct bs_tr *cur_ptr;
found = 0;
clrscr();
printf("\n\nEnter data item to search for :- ");
flushall();
scanf("%s",&s_item);
cur_ptr = root;
while ((cur_ptr != NULL) && (found == 0))
{
if (strcmp(s_item,cur_ptr->data) == 0)
{
found = 1;
}
if (strcmp(s_item,cur_ptr->data) < 0)
{
cur_ptr = cur_ptr->left;
}
if (strcmp(s_item,cur_ptr->data) > 0)
{
cur_ptr = cur_ptr->right;
}
}
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("Size of each node in bytes = %d\n",sizeof(struct bs_tr));
printf("Search for data = %s\n\n", s_item);
printf("\n\nData exists in the BST...Successful Search...");
getch();
}
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;
}