Hi,
In this "tree" code, what I am having trouble with is for example i inputted 2 numbers ( 7 and 5 ) an 7 is the root. if i wanted to delete 7 which is the root, it should be deleted and replaced by 5 making 5 the new root. But in my program, it instead deletes both 7 (the root) and 5 (the child) making the tree empty.
Please check my code below. Thanks!
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
struct tree
{
int data;
struct tree *left;
struct tree *right;
}*top,*a,*b, *temp;
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)
{
struct tree *p;
int new;
while(1)
{
if ( t==NULL )
{
printf("\n\n The number is NOT found!");
return;
}
else if ( t->data<num )
{
p=t;
t=t->right;
}
else if ( t->data>num )
{
p=t;
t=t->left;
}
else if ( t->data==num )
break;
}
if ( t->left==NULL && t->right==NULL )
caseA(p,t);
if ( t->left!=NULL && t->right==NULL )
caseB(p,t);
if ( t->left==NULL && t->right!=NULL )
caseB(p,t);
if ( location->left!=NULL && location->right!=NULL )
caseC(parent,location);
free(t);
if ( t==top )
t=top=NULL;
printf("\n\n %d is successfully deleted.",num);
}
caseA(struct tree *par,struct tree *loc )
{
if ( par==NULL ) /*item to be deleted is root node*/
top=NULL;
else
if ( loc==par->left )
par->left=NULL;
else
par->right=NULL;
}
caseB(struct tree *par,struct tree *loc)
{
struct tree *child;
/*Initialize child*/
if ( loc->left!=NULL && loc==top )
child=top;
if ( loc->right!=NULL && loc==top )
child=top;
if ( loc->left!=NULL ) /*item to be deleted has left child*/
child=loc->left;
else /*item to be deleted has right child */
child=loc->right;
if ( par==NULL ) /*Item to be deleted is root node*/
top=child;
else
if ( loc==par->left ) /*item is left child of its parent*/
par->left=child;
else /*item is right child of its parent*/
par->right=child;
}
caseC(struct tree *par,struct tree *loc)
{
struct tree *ptr,*ptrsave,*suc,*parsuc;
/*Find inorder successor and its parent*/
ptrsave=loc;
ptr=loc->right;
while ( ptr->left!=NULL )
{
ptrsave=ptr;
ptr=ptr->left;
}
suc=ptr;
parsuc=ptrsave;
if ( suc->left==NULL && suc->right==NULL )
caseA(parsuc,suc);
else
caseB(parsuc,suc);
if ( par==NULL ) /*if item to be deleted is root node*/
top=suc;
else
if ( loc==par->left )
par->left=suc;
else
par->right=suc;
suc->left=loc->left;
suc->right=loc->right;
}
int main()
{
int num, choice;
clrscr();
printf("\n Enter the root: ");
scanf("%d",& num);
top=make(num);
a=top;
do
{
clrscr();
printf("\n MAIN MENU\n");
printf("\n [1] Insert");
printf("\n [2] Delete");
printf("\n [3] Locate");
printf("\n [4] Traverse");
printf("\n [5] Exit");
printf("\n\n Enter the number of your choice: ");
scanf("%d",&choice);
switch(choice)
{
case 1: clrscr();
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);
}
getch();
break;
case 2: clrscr();
printf("\n\n Enter the number to delete: ");
scanf("%d",&num);
delete(top,num);
getch();
break;
case 3: clrscr();
printf("\n\n Enter the number to locate: ");
scanf("%d",&num);
locate(top,num);
getch();
break;
case 4: clrscr();
if (top==NULL)
printf("\n\n The tree is empty.");
else
{
printf("\n\nPreorder: ");
preorder(top);
printf("\n\nInorder: ");
inorder(top);
printf("\n\nPostorder: ");
postorder(top);
}
getch();
break;
case 5: clrscr();
printf("\n Good Bye!");
getch();
exit(0);
default: printf("\n\n Invalid Choice! Please try again.");
getch();
break;
}
} while ( choice!=5 );
getch();
return 0;
}