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

Maybe you should study this wiki article

I have already read that before. I know what a BST is and I know what the process is when deleting a node. My problem is putting it into C code with the current C program that I have come up with.

Please don't post a reply if you're just going to point me to various sites regarding BST rather than suggesting code tips regarding my BST C program.

Thanks anyway.

Easy does it Ellenski. If Ancient Dragon recommends something, I'd read it. He's one of the most knowledgeable posters you'll find.

I, on the other hand, know just about zip about BST's, but clearly you need to adjust the left and right pointers to the nodes that are linking to the node you want to delete. Otherwise, the tree would have a "sinkhole" in it.

Sight unseen, I'd bet you $$$ the article he mentioned, has the answer to that very question.

Why don't you read that article, and I'll do the same. If you're still stuck, post back and say what has you stumped, and what you tried, already.

;)

Edited 6 Years Ago by Adak: n/a

Yes, I have read that article before and I did read it again like you said.

My problem is that it is a lot more complicating to make a delete function when I am adding numbers in my void main(). It might not be that complicating if I put all of that in a "void insert()" function but since I didn't, it made it difficult for me to make my code.

I tried rewriting my code by using an insert function so that I wou;dn't have to put any of that in my void main() but my program wouldn't run and there were lots of errors. So I decided to stick with this code instead.

I wonder.... could you help me put all of that in an "insert()" function by the way I wrote my code? :)

Okay, I'll check back later.

I just finished making my programming assignment for my other subject and now I have to go to sleep. Need to be in school by 7:30am and it's already 1:43am right now.

Hope you have a great day ahead & thanks again. :)

Edited 6 Years Ago by ellenski: n/a

This is your code, changed to put the add a number, inside the menu. No help on delete yet, need to clear some more time for that one.

#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)
{

}

int main()
{
   int num, choice, loc;
   char ans;
   clrscr();
   printf("\n Enter the root: ");
   scanf("%d",& num);
   top=make(num);
   a=top;
   do
 	 {
      clrscr();
      printf("\n        MAIN MENU\n");
      printf("\n       [1] Traverse");
      printf("\n       [2] Locate");
      printf("\n       [3] Delete");
      printf("\n       [4] Add a Number");
      printf("\n       [5] 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 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 5: clrscr();
		        printf("\n   Good Bye!");
		        getch();
            exit(0);
            default: printf("\n\n Invalid Choice! Please try again.");
            getch();
            break;
      }
	 } while ( choice!=5 );
   getch();
   printf("\n\n\t\t\t    press enter when ready");
   choice=getchar();
   return 0;
}

If you'll change your IDE >options >Editor to use 2 or 3 spaces, instead of tabs, the formatting on the forum, and for myself, will go a lot better/faster. This looks rather sad.

Edited 6 Years Ago by Adak: n/a

There are three cases that have to be dealt with when you remove a node:

1) Node has no children (leaf node)
2) Node has one child node attached. Child must be attached to the parent of
the node being deleted
3) Node has two child nodes. Both nodes must be attached to the parent of
the node being deleted

This (hopefully!) covers the first two cases. Case #3 is basically the same as case
#2, so I'm leaving that one, for you.

I see why you had problem with this - every bit of info I could find on it, either glazed over the details, (especially for #1), or showed the details in C++ or Java, in OOP style programs.

#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)
{
   struct tree *p;  //the parent of t  
   /* locate the key */
   while(1) {
     if(t==NULL) {
       printf("\n Value 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;
   }  
   
   /* node has no children */
   if((t->left==NULL) && (t->right==NULL)) {
     if(p->left==t)
       p->left=NULL;
     else
       p->right=NULL;
     t=NULL;
     free(t);
   }          
   /* node has 1 child */
   else if((t->left && !t->right) || (t->right && !t->left)) {
     if(t->left) {
       p->left=t->left;
     }
     else {
       p->right=t->right;
     }
     t->right=NULL;
     t->left=NULL;
     t=NULL;
     free(t);
   }
}

int main()
{
   int num, choice, loc;
   char ans;
   clrscr();
   printf("\n Enter the root: ");
   scanf("%d",& num);
   top=make(num);
   a=top;
   do
 	 {
      clrscr();
      printf("\n        MAIN MENU\n");
      printf("\n       [1] Traverse");
      printf("\n       [2] Locate");
      printf("\n       [3] Delete");
      printf("\n       [4] Add a Number");
      printf("\n       [5] Exit");
      printf("\n\n Enter the number of your choice: ");
      scanf("%d",&choice);
      ans = getchar();
      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);
            printf("\n top=%p", top);
		        getch();
		        break;
         case 4: 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 5: clrscr();
		        printf("\n   Good Bye!");
		        getch();
            exit(0);
            default: printf("\n\n Invalid Choice! Please try again.");
            getch();
            break;
      }
	 } while ( choice!=5 );
   getch();
   printf("\n\n\t\t\t    press enter when ready");
   ans=getchar();
   ++ans;                    //just stops a stupid warning
   return 0;
}

Caution:
I have only tested this delete function on a few simple tree's, so check it out thoroughly.

There is C code out there for #2 and #3 however, I didn't use them since I wanted to understand it better. I've never coded up BST's, before.

This is your code, changed to put the add a number, inside the menu. No help on delete yet, need to clear some more time for that one.

#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)
{

}

int main()
{
   int num, choice, loc;
   char ans;
   clrscr();
   printf("\n Enter the root: ");
   scanf("%d",& num);
   top=make(num);
   a=top;
   do
 	 {
      clrscr();
      printf("\n        MAIN MENU\n");
      printf("\n       [1] Traverse");
      printf("\n       [2] Locate");
      printf("\n       [3] Delete");
      printf("\n       [4] Add a Number");
      printf("\n       [5] 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 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 5: clrscr();
		        printf("\n   Good Bye!");
		        getch();
            exit(0);
            default: printf("\n\n Invalid Choice! Please try again.");
            getch();
            break;
      }
	 } while ( choice!=5 );
   getch();
   printf("\n\n\t\t\t    press enter when ready");
   choice=getchar();
   return 0;
}

If you'll change your IDE >options >Editor to use 2 or 3 spaces, instead of tabs, the formatting on the forum, and for myself, will go a lot better/faster. This looks rather sad.

thanks, I'll give this a try.

There are three cases that have to be dealt with when you remove a node:

1) Node has no children (leaf node)
2) Node has one child node attached. Child must be attached to the parent of
the node being deleted
3) Node has two child nodes. Both nodes must be attached to the parent of
the node being deleted

This (hopefully!) covers the first two cases. Case #3 is basically the same as case
#2, so I'm leaving that one, for you.

I see why you had problem with this - every bit of info I could find on it, either glazed over the details, (especially for #1), or showed the details in C++ or Java, in OOP style programs.

#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)
{
   struct tree *p;  //the parent of t  
   /* locate the key */
   while(1) {
     if(t==NULL) {
       printf("\n Value 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;
   }  
   
   /* node has no children */
   if((t->left==NULL) && (t->right==NULL)) {
     if(p->left==t)
       p->left=NULL;
     else
       p->right=NULL;
     t=NULL;
     free(t);
   }          
   /* node has 1 child */
   else if((t->left && !t->right) || (t->right && !t->left)) {
     if(t->left) {
       p->left=t->left;
     }
     else {
       p->right=t->right;
     }
     t->right=NULL;
     t->left=NULL;
     t=NULL;
     free(t);
   }
}

int main()
{
   int num, choice, loc;
   char ans;
   clrscr();
   printf("\n Enter the root: ");
   scanf("%d",& num);
   top=make(num);
   a=top;
   do
 	 {
      clrscr();
      printf("\n        MAIN MENU\n");
      printf("\n       [1] Traverse");
      printf("\n       [2] Locate");
      printf("\n       [3] Delete");
      printf("\n       [4] Add a Number");
      printf("\n       [5] Exit");
      printf("\n\n Enter the number of your choice: ");
      scanf("%d",&choice);
      ans = getchar();
      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);
            printf("\n top=%p", top);
		        getch();
		        break;
         case 4: 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 5: clrscr();
		        printf("\n   Good Bye!");
		        getch();
            exit(0);
            default: printf("\n\n Invalid Choice! Please try again.");
            getch();
            break;
      }
	 } while ( choice!=5 );
   getch();
   printf("\n\n\t\t\t    press enter when ready");
   ans=getchar();
   ++ans;                    //just stops a stupid warning
   return 0;
}

Caution:
I have only tested this delete function on a few simple tree's, so check it out thoroughly.

There is C code out there for #2 and #3 however, I didn't use them since I wanted to understand it better. I've never coded up BST's, before.

Thank you so much for thaking the time to figure out a part of the delete function. I will give this a try. :) And you're right about why I had a problem with this.

There are three cases that have to be dealt with when you remove a node:

1) Node has no children (leaf node)
2) Node has one child node attached. Child must be attached to the parent of
the node being deleted
3) Node has two child nodes. Both nodes must be attached to the parent of
the node being deleted

This (hopefully!) covers the first two cases. Case #3 is basically the same as case
#2, so I'm leaving that one, for you.

I see why you had problem with this - every bit of info I could find on it, either glazed over the details, (especially for #1), or showed the details in C++ or Java, in OOP style programs.

#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)
{
   struct tree *p;  //the parent of t  
   /* locate the key */
   while(1) {
     if(t==NULL) {
       printf("\n Value 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;
   }  
   
   /* node has no children */
   if((t->left==NULL) && (t->right==NULL)) {
     if(p->left==t)
       p->left=NULL;
     else
       p->right=NULL;
     t=NULL;
     free(t);
   }          
   /* node has 1 child */
   else if((t->left && !t->right) || (t->right && !t->left)) {
     if(t->left) {
       p->left=t->left;
     }
     else {
       p->right=t->right;
     }
     t->right=NULL;
     t->left=NULL;
     t=NULL;
     free(t);
   }
}

int main()
{
   int num, choice, loc;
   char ans;
   clrscr();
   printf("\n Enter the root: ");
   scanf("%d",& num);
   top=make(num);
   a=top;
   do
 	 {
      clrscr();
      printf("\n        MAIN MENU\n");
      printf("\n       [1] Traverse");
      printf("\n       [2] Locate");
      printf("\n       [3] Delete");
      printf("\n       [4] Add a Number");
      printf("\n       [5] Exit");
      printf("\n\n Enter the number of your choice: ");
      scanf("%d",&choice);
      ans = getchar();
      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);
            printf("\n top=%p", top);
		        getch();
		        break;
         case 4: 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 5: clrscr();
		        printf("\n   Good Bye!");
		        getch();
            exit(0);
            default: printf("\n\n Invalid Choice! Please try again.");
            getch();
            break;
      }
	 } while ( choice!=5 );
   getch();
   printf("\n\n\t\t\t    press enter when ready");
   ans=getchar();
   ++ans;                    //just stops a stupid warning
   return 0;
}

Caution:
I have only tested this delete function on a few simple tree's, so check it out thoroughly.

There is C code out there for #2 and #3 however, I didn't use them since I wanted to understand it better. I've never coded up BST's, before.

I have a question about your code. If I have deleted all the numbers and the only one that's left is the root.

Will it fall under this code for it to be deleted?:

/* node has no children */
if((t->left==NULL) && (t->right==NULL)) {
   if(p->left==t)
      p->left=NULL;
   else
      p->right=NULL;
   t=NULL;
   free(t);
}

I'm asking because I noticed that if the root is left after deleting all the numbers, the root can't be deleted with your code above.

Or, do I have to add something like the code below for it to be deleted?:

/* delete root if only root is in the tree */
if (p==num)
   t=NULL;
else
   if (t==p->left)
      p->left=NULL;
   else
      p->right=NULL;

I know the code above doesn't work right yet because I tried it. I'm just using it as an example.

Thanks again. :)

Edited 6 Years Ago by ellenski: n/a

I have some important errands to run, just now. I'll take a look at this when i get back (2 hours).

If the root is not being deleted, then it appears that either the left or right child has not been set to NULL, as it should have been,

OR

t is never being set to the true root.

Back after bit. Let's keep our Deerstalking caps, close at hand:

"Come, Watson! The game is afoot!" ;)

The problem with deleting the root was that we're working with t, but "top" is the real boss address, and it is a global.

So this is the logic to handle that, warts and all:

void delete(struct tree *t, int num)
{
   struct tree *p;  //the parent of t  
   /* locate the key */
   while(1) {
     if(t==NULL) {
       printf("\n Value 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;
   }  
   
   /* node has no children */
   if((t->left==NULL) && (t->right==NULL)) {
     if(p->left==t)
       p->left=NULL;
     else
       p->right=NULL;
//     t=NULL;
//     free(t);
   }          
   /* node has 1 child */
   else if((t->left && !t->right) || (t->right && !t->left)) {
     if(t->left) {
       p->left=t->left;
     }
     else {
       p->right=t->right;
     }
     t->right=NULL;
     t->left=NULL;
//     t=NULL;
//     free(t);
   }

   /* node has two children */
   /*  888888888888888888888 Working here! 88888888888888888888888
   else {
     if(p->left==t) {
       t->data=t->left.data;
       /* to be continued ;) */

     }
     else 
   }
   */

   /* is node the root? */
   if(t==top) {
     t=top=NULL;
     free(t);
   }
   else {
     t=NULL;
     free(t);
   }
}

The problem with deleting the root was that we're working with t, but "top" is the real boss address, and it is a global.

So this is the logic to handle that, warts and all:

void delete(struct tree *t, int num)
{
   struct tree *p;  //the parent of t  
   /* locate the key */
   while(1) {
     if(t==NULL) {
       printf("\n Value 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;
   }  
   
   /* node has no children */
   if((t->left==NULL) && (t->right==NULL)) {
     if(p->left==t)
       p->left=NULL;
     else
       p->right=NULL;
//     t=NULL;
//     free(t);
   }          
   /* node has 1 child */
   else if((t->left && !t->right) || (t->right && !t->left)) {
     if(t->left) {
       p->left=t->left;
     }
     else {
       p->right=t->right;
     }
     t->right=NULL;
     t->left=NULL;
//     t=NULL;
//     free(t);
   }

   /* node has two children */
   /*  888888888888888888888 Working here! 88888888888888888888888
   else {
     if(p->left==t) {
       t->data=t->left.data;
       /* to be continued ;) */

     }
     else 
   }
   */

   /* is node the root? */
   if(t==top) {
     t=top=NULL;
     free(t);
   }
   else {
     t=NULL;
     free(t);
   }
}

is the code:

if(t==top)
{
   t=top=NULL;
   free(t);
}
else
{
   t=NULL;
   free(t);
}

supposed to delete the root already?

..because I tried it and it didn't work. I even tried editing the above code a little bit but still it didn't work. I also tried deleting the root from the main() part of the program (meaning in the switch case part) using a different but similar code, and still it didn't work. :(

Did you use the whole delete function? Because there are a few other changes to it, as well.

Yes, the delete function now deletes the root, IF t==top, in the program. Ran it 5 times - worked every time. Did not test with negative numbers, however.

There may be a problem with nested comments:

/*

/* */

else
*/

being handled differently on our compiler's. I see the forum software doesn't allow them (the else in my post above is not green, and should be).

Let me see what's up with that.

What numbers failed for you?

Delete lines 45 through lines 56 (which is just my doodling with some code anyway), and then re-run it. It still works fine for me, how about you, now?

Edited 6 Years Ago by Adak: n/a

Did you use the whole delete function? Because there are a few other changes to it, as well.

Yes, the delete function now deletes the root, IF t==top, in the program. Ran it 5 times - worked every time. Did not test with negative numbers, however.

There may be a problem with nested comments:

/*

/* */

else
*/

being handled differently on our compiler's. I see the forum software doesn't allow them (the else in my post above is not green, and should be).

Let me see what's up with that.

What numbers failed for you?

Delete lines 45 through lines 56 (which is just my doodling with some code anyway), and then re-run it. It still works fine for me, how about you, now?

It works now. No wonder it didn't work before, I was able to delete the code in green. The ones after the //. I remember that // gave me an error that's why I deleted them without thinking that it was suppose to be like a comment (not included with the code) because I just remembered that // only works in C++.

Now the only thing left is for deleting a node with 2 children. Based on what I've read, I'm guessing/thinking that the code for this might be quite longer?

Actually, // for comments has worked for C in old Turbo C (my version is 1.01), and now is part of the C99 standard.

Yes, it will be longer, since one of the child nodes must be "moved up", to become the new parent, and be "attached" to the grandparent node. (the p pointer points to the grandparent, in the delete function).

The other child node becomes a child of the new parent.

To avoid long term "left single" or "right single" threads, the choice of which node should be moved to parent in this case, should alternate. A rather fine point, to be sure, only for long term BST use by a program.

Yes, I've been reading! ;)

Actually, // for comments has worked for C in old Turbo C (my version is 1.01), and now is part of the C99 standard.

Yes, it will be longer, since one of the child nodes must be "moved up", to become the new parent, and be "attached" to the grandparent node. (the p pointer points to the grandparent, in the delete function).

The other child node becomes a child of the new parent.

To avoid long term "left single" or "right single" threads, the choice of which node should be moved to parent in this case, should alternate. A rather fine point, to be sure, only for long term BST use by a program.

Yes, I've been reading! ;)

hi again.

i have figured out a bit on how to delete but not completely. the only problem i have left is if for example i inputted 2 numbers ( 7 and 5 ) an 7 is the root. if i want 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.

here's my code:

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

Edited 6 Years Ago by ellenski: n/a

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