Hi,
We were asked to make a Binary Search Tree program in C. It should be able to traverse the numbers (preorder, inorder, postorder) then display it. And locate the number and display it. And locate the number to delete, delete it, then display the number that was deleted before going back to the "MAIN MENU".
I am able to traverse it and locate the number I want to locate. But for the delete function, I don't know where to begin or how to start it. Any suggestions would be really appreciated. Thanks! Here's my complete working code without anything in the delete function:
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
struct tree
{
int data;
struct tree *left;
struct tree *right;
}*top,*a,*b;
struct tree *make(int m)
{
struct tree *newnode;
newnode=(struct tree *)malloc(sizeof(struct tree));
newnode->data=m;
newnode->right=newnode->left=NULL;
return(newnode);
}
void left(struct tree *t,int x)
{
if(t->left!=NULL)
printf("\n Invalid!");
else
t->left=make(x);
}
void right(struct tree *t,int x)
{
if(t->right!=NULL)
printf("\n Invalid!");
else
t->right=make(x);
}
void inorder(struct tree *t)
{
if(t!=NULL)
{
inorder(t->left);
printf("\t %d",t->data);
inorder(t->right);
}
}
void preorder(struct tree *t)
{
if(t!=NULL)
{
printf("\t %d",t->data);
preorder(t->left);
preorder(t->right);
}
}
void postorder(struct tree *t)
{
if(t!=NULL)
{
postorder(t->left);
postorder(t->right);
printf("\t %d",t->data);
}
}
void locate(struct tree *t, int num)
{
if ( t==NULL )
{
printf("\n\n The number is NOT found!");
}
else
{
if ( t->data==num )
printf("\n\n The number is found.");
else if ( t->data<num )
locate(t->right,num);
else
locate(t->left,num);
}
}
void delete(struct tree *t, int num)
{
}
void main()
{
int num, choice, loc;
char ans;
clrscr();
printf("\n Enter the root: ");
scanf("%d",& num);
top=make(num);
a=top;
do
{
printf("\n\n Add another number?(Y/N): ");
scanf(" %c",&ans);
if ( ans=='y' || ans=='Y' )
{
printf("\n Enter a number: ");
scanf("%d",&num);
if ( num==-1 )
break;
a=top;
b=top;
while ( num!=a->data && b!=NULL )
{
a=b;
if ( num<a->data )
b=a->left;
else
b=a->right;
}
if ( num<a->data )
{
printf("\n Left branch of %d is %d",a->data,num);
left(a,num);
}
else
{
right(a,num);
printf("\n Right Branch of %d is %d",a->data,num);
}
}
else
{
do
{
clrscr();
printf("\n MAIN MENU\n");
printf("\n [1] Traverse");
printf("\n [2] Locate");
printf("\n [3] Delete");
printf("\n [4] Exit");
printf("\n\n Enter the number of your choice: ");
scanf("%d",&choice);
switch(choice)
{
case 1: clrscr();
printf("\n\nPreorder: ");
preorder(top);
printf("\n\nInorder: ");
inorder(top);
printf("\n\nPostorder: ");
postorder(top);
getch();
break;
case 2: clrscr();
printf("\n\n Enter the number to locate: ");
scanf("%d",&num);
locate(top,num);
getch();
break;
case 3: clrscr();
printf("\n\n Enter the number to delete: ");
scanf("%d",&num);
delete(top,num);
getch();
break;
case 4: clrscr();
printf("\n Good Bye!");
getch();
exit(0);
default: printf("\n\n Invalid Choice! Please try again.");
getch();
break;
}
} while ( choice!=4 );
}
} while ( ans=='y' || ans=='Y' );
getch();
}