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;
}

On just a quick review, does this version even compile without error? Lines 115 and 116 use variables which are not defined locally: parent and location.

If the condition in line 105 is true on the first pass through the loop, p will not be initialized when used in lines 109 to 114. Since it is an automatic variable, it could have any value and not necessisarily NULL.

On just a quick review, does this version even compile without error? Lines 115 and 116 use variables which are not defined locally: parent and location.

If the condition in line 105 is true on the first pass through the loop, p will not be initialized when used in lines 109 to 114. Since it is an automatic variable, it could have any value and not necessisarily NULL.

i forgot that i was using p and t. lines 115 and 116 is supposed to be:

if ( t->left!=NULL && t->right!=NULL )
      caseC(p,t);

that should now work without errors. but my problem still won't be resolved. please review my code again. thanks. :)

i forgot that i was using p and t. lines 115 and 116 is supposed to be:
.
.
.
please review my code again. thanks. :)

My second comment was directly related to the case you gave. It may not be the only problem for that case, but start by fixing it.

My second comment was directly related to the case you gave. It may not be the only problem for that case, but start by fixing it.

Are you talking about CaseC ? Can you give me some suggestions please? I'd really appreciate it. Thanks! =)

...
If the condition in line 105 is true on the first pass through the loop, p will not be initialized when used in lines 109 to 114. Since it is an automatic variable, it could have any value and not necessisarily NULL.

No I am not talking about CaseC(). I am talking about your while loop in delete(). I am quoting myself:

"If the condition in line 105 is true on the first pass through the loop, p will not be initialized when used in lines 109 to 114. Since it is an automatic variable, it could have any value and not necessisarily NULL."

For the example you gave: Insert 7, Insert 5, Delete 7, the condition on line 105 "( t->data==num )" will be true on the first pass through the while loop in delete( ) and p will not be initialized.

Edited 6 Years Ago by pheininger: Quoted the condition on line 105.

How about giving us some idea of which part of the code is not working ...
You know some thing of the sort this should be the expected O/P and this is what I am getting ......

This article has been dead for over six months. Start a new discussion instead.