Description In this lab your goal is to implement standard operations on binary
ID: 3586397 • Letter: D
Question
Description In this lab your goal is to implement standard operations on binary search trees, including insert and delete. See section 12.3 in the textbook. A sample class structure with empty methods, is given in the support code. You can either use the given class structure or create your own. In this assignment the keys are integers. You will use Grade04 to test your code. Your execution file name must be "BST.exe". Refer to the previous lab assignments for instructions on how to use the grading tool The input contains one of the following commands on a line » i key: Insert key into the BST. For example, "i 2" means "Insert key 2 into the BST" » d key: Delete key from the BST. For example, "d 2" means "Delete key 2 from the BST" Do nothing if the BST does not contain the key Output all keys in preorder » post: Output all keys in postorder in: Output all keys in inorder Finish your program Examples of input and output Input 1 i 5 i 7 d 7 d 7 pre d 1 postExplanation / Answer
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<process.h>
struct tree
{
struct tree *left;
int info;
struct tree *right;
};
void insert(struct tree **ptr,int item)
{
if(*ptr==NULL)
{
*ptr=(struct tree *)malloc(sizeof(struct tree));
(*ptr)->left=(*ptr)->right=NULL;
(*ptr)->info=item;
return;
}
else
{
if(item<(*ptr)->info)
{
insert(&((*ptr)->left),item);
}
else
{
insert(&((*ptr)->right),item);
}
return;
}
}
void delete_tree(struct tree **ptr,int item)
{
struct tree *move,*back,*temp;
if(*ptr==NULL)
{
printf("nEmpty tree..............n");
return;
}
else
{
move=*ptr;
back=move;
while(move->info!=item)
{
back=move;
if(item<move->info)
{
move=move->left;
}
else
{
move=move->right;
}
}
if(move->left!=NULL&&move->right!=NULL)
{
temp=move->right;
while(temp->left!=NULL)
{
back=temp;
temp=temp->left;
}
move->info=temp->info;
move=temp;
}
if(move->left==NULL&&move->right==NULL)
{
if(back->right==move)
{
back->right=NULL;
}
else
{
back->left=NULL;
}
free(move);
return;
}
if(move->left==NULL&&move->right!=NULL)
{
if(back->left==move)
{
back->left=move->right;
}
else
{
back->right=move->right;
}
free(move);
return;
}
if(move->left!=NULL&&move->right==NULL)
{
if(back->left==move)
{
back->left=move->left;
}
else
{
back->right=move->left;
}
free(move);
return;
}
}
}
void preorder(struct tree *ptr)
{
struct tree *move;
move=ptr;
if(move!=NULL)
{
printf(" %d ",move->info);
preorder(move->left);
preorder(move->right);
}
else
return;
}
void inorder(struct tree *ptr)
{
struct tree *move;
move=ptr;
if(move!=NULL)
{
inorder(move->left);
printf(" %d ",move->info);
inorder(move->right);
}
else
return;
}
void postorder(struct tree *ptr)
{
struct tree *move;
move=ptr;
if(move!=NULL)
{
postorder(move->left);
postorder(move->right);
printf(" %d ",move->info);
}
else
return;
}
void main()
{
clrscr();
struct tree *root=0;
int item,ch,order;
char choice,ch1;
clrscr();
do
{
printf(" n____________Tree MENU_______________nn");
printf(" i.Insert.n");
printf(" d.Delete.n");
printf(" n.Inorder.n");
printf(" r.Preorder.n");
printf(" o.Postorder.n");
printf(" e.Exit.n");
printf(" Enter your choice : ");
ch1=getche();
switch(ch1)
{
case 'i':
scanf("%d",&item);
insert(&root,item);
break;
case 'd':
scanf("%d",&item);
delete_tree(&root,item);
break;
case 'r': preorder(root);
break;
case 'n': inorder(root);
break;
case 'o': postorder(root);
break;
case 'e': exit(0);
}
fflush(stdin);
}while(ch!=4);
}