Solved

Binary Search tree functions-trouble with delete

Posted on 2003-11-25
17
422 Views
Last Modified: 2010-04-15
This is an assignment and I have worked on it extensively, but I can't get it to work correctly.I don't know why I get a 0 value when I print the tree after a delete of a node with two children. Also, after a couple of operations, it I get what looks to be an address value in the print. Can anyone tell me what I am doing wrong?  Oh, the trick here is that the tree is built in reverse with the larger value on the left and the smaller on the right. Here is what I have done:

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

#define SIZE 15
//Binary Search Tree function
//built in reverws


 struct Node
 {
    int data;
    struct Node *lchild;
    struct Node *rchild;
  };


/****************************function prototypes********************************/
struct Node * makeNode(int value); //create node
void addNode(struct Node **Rootptr, struct Node *newNode);      //insert node into BS
void deleteNode(struct Node **Rootptr, int value);       //delete node=-1 on failure =0 on success
void preOrderTraversal(struct Node *Rootptr); //perform preorder traversal
void inOrderTraversal(struct Node *Rootptr); //perform inorder traversal
void postOrderTraversal(struct Node *Rootptr); //perform postorder traversal
int Search(struct Node *Rootptr, int value);
//void deleteTree(struct Node *parent); //destroy tree parent

//*******************************  MAIN *****************************************
int main()
{

            struct Node *Rootptr=NULL;
            struct Node *newNode;
            char inputString[5], pString[5];
            char ch;
            char *charPtr;
            int number, found;
            int i;
            int ar[]={60, 75, 40, 32, 55, 80, 70, 74, 68, 69, 85, 90, 84, 65, 28};


           //make node & build tree
            for(i=0; i < SIZE;i++)
            {
               newNode=makeNode(ar[i]);
               addNode(&Rootptr, newNode);
             }

             printf("\nEnter one of the following characters followed by an integer\n");
             printf("Enter a or A (Add node)\n");
             printf("Enter d or D (Delete node)\n");
             printf("Enter s or S (Delete node with same value)\n");
             printf("Enter p or P (Print all three traversals)\n");
             printf("Enter e or E to quit\n");
             printf("\n");

                 do{
                    gets(inputString);
                    ch=inputString[0];    //parse string to alpha
                    number=atoi(inputString+1);        //parse string to int

                    switch(toupper(ch))
                   {
                    case 'A':
                      newNode=makeNode(number);
                      printf("The numeric value is %d\n", newNode->data);
                      addNode(&Rootptr, newNode);
                      break;
                    case 'D':

                        deleteNode(&Rootptr, number);

                       // else
                          //  printf("Item not in tree");
                       break;
                    case 'S':
                       printf("Same\n");
                       break;
                     case 'P':

                      //perform traversals
                        printf("Preorder Traversal: ");
                        preOrderTraversal(Rootptr);
                        printf("\n");

                        printf("Inorder Traversal: ");
                        inOrderTraversal(Rootptr);
                        printf("\n");


                        printf("Postorder Traversal: ");
                        postOrderTraversal(Rootptr);
                        printf("\n");
                        printf("\n");
                        break;
                   case 'E':
                         break;
                   default:
                      printf("invalid entry, please re-renter\n");
                 }
                 }while(toupper(ch) != 'E');

                 

      system("PAUSE");
      return 0;
}

//**************************  FUNCTIONS   ***************************************/
struct Node *makeNode(int value)
  {
     struct Node *treeNode;

     treeNode=(struct Node *)malloc(sizeof(struct Node));
            if(treeNode==0){
            printf("Memory allocation error");
            return 0;         //early exit
            }

         treeNode->data=value;
         treeNode->lchild=NULL;
         treeNode->rchild=NULL;


        return treeNode;
   }
//***************************************************************************************
void addNode(struct Node **Rootptr, struct Node *newNode)
{
      struct Node *currPtr;

      int finished=0;

                if(*Rootptr==NULL) {        //if tree is empty
               *Rootptr=newNode;        //assign newNode to currptr
               }
            else
               {
               finished=0;
               currPtr=*Rootptr;
               while(finished == 0)                      //while not finished
              {
                 if(newNode->data <= currPtr->data)     //if value is less than root data
                 {
                     if(currPtr->rchild != NULL)        //if position to insert has not beens found
                        currPtr= currPtr->rchild;         //  traverse till null position is found in rchild
                     else
                     {
                      (currPtr->rchild)=newNode;         //else rchild is null-assign newNode to rchild
                       finished=1;
                     }
                 }//end if
                 else{                                     //otherwise, value is greater than root-go left
                     if(currPtr->lchild != NULL)           //position in lchild not yet found
                        currPtr=currPtr->lchild;           //traverse till position is found in lchild
                     else
                       {
                       (currPtr)->lchild=newNode;          //else lchild is null-assign newNode
                        finished=1;
                       }
                      }//end else
                   }//end whilw
                 }//end else
}

/****************************************************************************/

int Search(struct Node *Rootptr, int value)
  {
    struct Node *deleteNodePtr=Rootptr;
    int found=0;
      printf("%d ", value);
     if (value == deleteNodePtr->data)
       found= 1;
     else{
        while(found == 0 && deleteNodePtr !=NULL)   //while not found and root not null
        {
                 if(value <= deleteNodePtr -> data)
                      deleteNodePtr = deleteNodePtr -> rchild;
                  else
                      deleteNodePtr = deleteNodePtr ->lchild;

         }//end while
         printf("%d ", deleteNodePtr->data);
       }
       return found;

}



//******************************* delete function *******************************************//

//immediate predecessor-node containing smallest value in the tree
//greater than the value in node being deleted

void deleteNode(struct Node **Rootptr, int value)
{
        struct Node *parentPtr, *deleteNodePtr, *currPtr, *tempPtr, *tempParentPtr;   //define pointers
        int found=0;
        deleteNodePtr = *Rootptr;
        currPtr=deleteNodePtr;

         if(currPtr==NULL)
            printf("Tree is empty");

         if(currPtr !=NULL)
          {

                 while(currPtr->data != value)
                 {
                    if(currPtr -> data < value)
                    {
                    parentPtr=currPtr;
                    currPtr=currPtr->lchild;
                    }
                   else
                    {
                       parentPtr=currPtr;
                       currPtr=currPtr->rchild;
                     }

                    found=1;
                 } //end while


                if(found==1)
                 {
                     printf("the value to delete is %d\n", currPtr->data);

                          if(currPtr->lchild == NULL && currPtr->rchild == NULL)   //if node is a leaf
                          {                                                         //reset pointer in parent node to NULL and free memory
                              printf("Value %d has 2 null pointers", currPtr->data);
                               if(currPtr==*Rootptr)                                  //if item to delete is the rootptr
                               {
                                   printf("This node is the root of the tree\n");
                                   Rootptr=NULL;                                       //set rootptr to null and delete currptr
                                   free(currPtr);
                               }
                               else
                               {
                                  if (parentPtr->lchild==currPtr){
                                  parentPtr->lchild=NULL;
                                  free(currPtr);
                                  }
                                  else{
                                  parentPtr->rchild=NULL;
                                  free(currPtr);
                                  } //end else
                              } //end else
                          } //end if

                          else if(currPtr->lchild == NULL && currPtr->rchild != NULL) //case2 value to delete has null left child
                         {
                             printf("Value to delete %d has one null child\n", currPtr->data);
                                   if(parentPtr->rchild==currPtr)
                                    {
                                     parentPtr->rchild = currPtr->rchild;
                                     free(parentPtr);
                                    } //end if
                                   else if(parentPtr->lchild==currPtr)
                                   {
                                     parentPtr->lchild=currPtr->lchild;
                                     free(parentPtr);
                                   } //end else

                            } //end else if


                           //else if right child null and left child not null
                           else if(currPtr->rchild == NULL &&  currPtr->lchild !=NULL)
                            {
                             printf("Value %d has null right child and value left child is %d" ,currPtr->data, *(currPtr)->lchild);
                               if(parentPtr->lchild = currPtr)
                               {
                                    parentPtr->lchild=currPtr->lchild;
                                    free(parentPtr);
                               }
                              else
                             {
                               parentPtr->rchild=currPtr->lchild;
                               free(parentPtr);
                             } //endelse

                          }


                      else{
                      printf("Value to delete %d has two children\n", currPtr->data);
                      tempPtr=currPtr->rchild;

                             while(tempPtr->lchild != NULL)
                             {
                             tempParentPtr=tempPtr;
                             tempPtr=tempPtr->lchild;
                             }

                            tempPtr=currPtr;
                            printf("currPtr value is now %d", currPtr->data);
                            if (currPtr->lchild==NULL )
                            {
                               if(tempParentPtr->rchild==currPtr)
                                       tempParentPtr->rchild=currPtr->rchild;
                               else
                                       tempParentPtr->lchild=currPtr->rchild;
                            }
                           free(tempParentPtr);
                           ;
                        }//endif

                    }
              }
}
 /**************************** Traversals **********************************/

void inOrderTraversal(struct Node *Rootptr)
{
      if(Rootptr!=NULL)
      {
      inOrderTraversal(Rootptr->lchild);
      printf(" %d", Rootptr->data);
      inOrderTraversal(Rootptr->rchild);
      }

}

void preOrderTraversal(struct Node *Rootptr)
{
     if(Rootptr!=NULL)
     {
     printf(" %d", Rootptr->data);
     preOrderTraversal(Rootptr->lchild);
     preOrderTraversal(Rootptr->rchild);
     }
}

void postOrderTraversal(struct Node *Rootptr)
{
      if(Rootptr!=NULL)
      {
      postOrderTraversal(Rootptr->lchild);
      postOrderTraversal(Rootptr->rchild);
      printf(" %d", Rootptr->data);
      }

}




































































0
Comment
Question by:closet
17 Comments
 
LVL 16

Expert Comment

by:imladris
ID: 9818939
Well, I haven't actually run this (yet). However I note that you say the tree is built in reverse, with the larger value on the left. I find that to be true in the addNode function. However, in the deleteNode function, the initial search loop goes left for smaller values:

                 while(currPtr->data != value)
                 {
                    if(currPtr -> data < value)
                    {
                    parentPtr=currPtr;
                    currPtr=currPtr->lchild;
                    }
                   else
                    {
                       parentPtr=currPtr;
                       currPtr=currPtr->rchild;
                     }

                    found=1;

I expect that will cause some kind of trouble.
0
 
LVL 45

Expert Comment

by:Kdo
ID: 9818983


Delete() needs help.  :)


To delete the node, you need to merge the two branches underneath it.  You seem to be doing this.

Once the branches are merged, you need to replace the parentPtr->lnode OR the parentPtr->rnode pointer with the new "head of the branch" node.



Kent
0
 
LVL 16

Expert Comment

by:imladris
ID: 9819028
Certainly, the reversal I thought was there isn't. My apologies. The values being compared were arranged opposite, and so the comparison operator was also reversed; no problem there.
0
 
LVL 16

Expert Comment

by:imladris
ID: 9819205
Actually, the merge isn't happening either. Make a picture of the tree and follow along. If you try to delete node 75 (the root is 60, left under that is 75, left under 75 is 80, and right under 75 is 70 etc.),
the two children case sets tempPtr to  75's right child, which is 70. Then in the loop it goes down the left side until the end, so it winds up going down one level to node 74.
tempPtr is then *reset* to currPtr, which is still 75 (which is what the printf reports).
Then it checks if currPtr's left node is NULL (which it isn't, 75 has node 80 on its left).
And since it isn't, it simply deletes node 75.

To do the merge, you need to do something like go down the left from 75 looking for a right that is NULL. When you find one, you need to make it point to 75's right node instead. So, for instance, in this case that would mean finding node 80 has a free right, and making it point to 70.

Then you need to hook the parent pointer, to the new head, which is the left child of the deleted node, which is node 80. Then free 75.

0
 
LVL 16

Expert Comment

by:imladris
ID: 9819268
A correction here. You can't simply go down the left looking for a free right. To merge properly you would have to "search" starting at the left, and go down left or right based on comparisons until you find the appropriate free node. In this particular case, 80 is still the node to attach it to. But if 80 had had a right child of 76, then you would have had to go right at 80, and and there, since 76's right node was NULL.
0
 
LVL 16

Expert Comment

by:imladris
ID: 9825347
Did any of those answers help?

If so it is now time to select one (or more) and grade it to close the question.

If not, perhaps a clarifying question would help.
0
 

Author Comment

by:closet
ID: 9825918
I didn't have time on Tuesday to do more than check in to see what responses were in my box.  Looking over the comments from imladris & kdo, but haven't had time to implement.I expect to get back to work on it Wed afternoon and will have more comments or questions. I think I understand what is being said, but I won't be sure until I actually do it. Thanks,
Closet
0
 
LVL 17

Expert Comment

by:rstaveley
ID: 9830825
Line 275:  if(parentPtr->lchild = currPtr)

That's an assignment.
0
Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

 

Author Comment

by:closet
ID: 9846941
I am still not quite understanding the merge. If I use the immediate predecessor to the node to be deleted- say in this case I want to delete 75.  I want to find the largest value previous to 75. That is 74.
I should be able to copy 74 to currPtr and have that replace 75 without breaking the way the tree is connected. Then I should just be able to assign the tempPtr->rchild and tempPtr->lchild values to the tempParentPtr.  In this case they are both null values. Then delete the tempPtr. This is still not working.

So this is what I have done:
  else{
                      printf("Value to delete %d has two children\n", currPtr->data);
                      printf("Value of parentPtr is %d\n", parentPtr->data);
                      tempPtr=currPtr->rchild;
                      printf("tempPtr is %d\n", tempPtr->data);
                             while(tempPtr->rchild != NULL)
                             {
                             tempParentPtr=tempPtr;
                             printf("tempParentPtr is %d", tempParentPtr->data);
                             tempPtr=tempPtr->lchild;
                             printf("\ntempPtr is %d", tempPtr->data);
                             }

                            currPtr=tempPtr;
                            printf("\ncurrPtr value is now %d", currPtr->data);
                            if(tempPtr->rchild==NULL) {
                                  if(parentPtr->lchild==currPtr)
                                     tempParentPtr->lchild=tempPtr->rchild;

                                  else
                                     tempParentPtr->lchild=tempParentPtr->lchild;
                             }
                             else{
                                  if(tempPtr->lchild==NULL)
                                    if(parentPtr->lchild= currPtr)
                                      tempParentPtr->rchild=tempPtr->rchild;

                                    else
                                     tempParentPtr->rchild=tempParentPtr->lchild;
                                }
                             free(tempPtr);
                        }//endif

                    }
              }
}

To merge properly you would have to "search" starting at the left, and go down left or right based on comparisons until you find the appropriate free node. In this particular case, 80 is still the node to attach it to. But if 80 had had a right child of 76, then you would have had to go right at 80, and and there, since 76's right node was NULL.

I am not sure what value I am searching for in this explanation. If 76 is in the tree, the would be the immediate successor, correct? As I have done the program using the immediate predecessor, can you tell me what I am doing wrong there?
Thanks


0
 
LVL 16

Expert Comment

by:imladris
ID: 9851035
OK, let's start by going through your code line by line. Have a drawing of the tree handy to refer to.

  else{
                      printf("Value to delete %d has two children\n", currPtr->data);
                      printf("Value of parentPtr is %d\n", parentPtr->data);

currPtr is pointing to the node holding 75, as the printf indicates

                      tempPtr=currPtr->rchild;
                      printf("tempPtr is %d\n", tempPtr->data);

tempPtr is pointing to the node holding 70, which the printf confirms

Now tempPtr->rchild is pointing to node 68 which is not NULL, so the while loop is entered

                             while(tempPtr->rchild != NULL)
                             {
                             tempParentPtr=tempPtr;
                             printf("tempParentPtr is %d", tempParentPtr->data);

tempParentPtr is set to point to node 70, which the printf confirms

                             tempPtr=tempPtr->lchild;
                             printf("\ntempPtr is %d", tempPtr->data);

tempPtr is advanced down the *left* side to point to 74

                             }

Now currPtr is set to point to 74. Note that this does *not* change the structure of the tree. The rootnode is not affected, nor its lchild or rchild pointers, nor any other nodes.

                            currPtr=tempPtr;
                            printf("\ncurrPtr value is now %d", currPtr->data);

tempPtr is pointing to node 74, its rchild is NULL, so the if is entered

                            if(tempPtr->rchild==NULL) {

parentPtr->lchild is still node 75. It is not equal to node 74, so the else is executed

                                  if(parentPtr->lchild==currPtr)
                                     tempParentPtr->lchild=tempPtr->rchild;

                                  else

tempParentPtr is node 70. This assignment sets its left child to its left child; so it stays the same.

                                     tempParentPtr->lchild=tempParentPtr->lchild;
                             }

this else is not executed
                             else{
                                  if(tempPtr->lchild==NULL)
                                    if(parentPtr->lchild= currPtr)
                                      tempParentPtr->rchild=tempPtr->rchild;

                                    else
                                     tempParentPtr->rchild=tempParentPtr->lchild;
                                }

Now we are at the end of this clause. The tree structure has not been altered in any way. Now you free node 75. Now the tree is broken.

                             free(tempPtr);
                        }//endif

                    }
              }
}


If you want to use 74 to substitute for 75 to avoid changing the structure of the tree higher up, you would have to do something like the following:

Instead of currPtr=tempPtr, you would write:

currPtr->data=tempPtr->data

This will *change* node 75 to now contain a 74. Then you will have to delete node 74. This will involve changing the lchild of node 70 (tempParentPtr) to NULL, and freeing node 74 (tempPtr).

0
 
LVL 16

Expert Comment

by:imladris
ID: 9851096
Note that I'm not sure of the general algorithm for this kind of merge.

Note that you are searching for the node to substitute for the deleted node with a loop that relies purely on finding a node whose rchild is NULL. It assumes that such a node has a lchild that is not NULL. Imagine, for instance, what would happen if there were a 73 in the tree. It would wind up being 74's rchild. I'm not sure how you would deal with that. I'm not saying it's not possible; I'm saying I'm not sure how it would be done; and you'll have to deal with that case somehow.

I have been proposing a different algorithm for merging the subtrees. With 75 soon to be gone you have two subtrees; one with a root of 80, one with a root of 70. What I propose is that you go down the "80" subtree, looking for where 70 would go. So you search down the subtree; 70 is less than 80 so you go right; that's NULL, so you can point the rchild of 80 to the root of the 70 subtree and, voila, the two are merged. Then you just need to point the lchild of 60 (parentPtr) to node 80, delete 75, and you're done.

As a slightly more elaborate example, suppose there had been a node 76. It would have been node 80's rchild. Now search for "70" down the 80 subtree. It is less, so go right. Now we are at node 76. 70 is less than 76 as well so go right. This is NULL, so make it point to the 70 subtree, and then proceed as before.
0
 

Author Comment

by:closet
ID: 9853673
imladris
thank you for that. I see that I needed the currPtr->data =tempPtr->data part. That made a huge difference...
I learned that to find the immediate predecessor in a normal tree you go left all the way to the right. So that should answer your comment about the 73 I think. But I don't have the solution yet for when a replacement value has a right child and no left child. (Is that what you meant?)

I am trying that out now and if I can't get it to work I will go with your approach to merging the subtrees. I think imladris' 12/01 coment will be the one I accept but will wait til I am through with this next phase. Thanks so much for all your input.

closet
0
 
LVL 16

Expert Comment

by:imladris
ID: 9853931
>But I don't have the solution yet for when a replacement value has a right child and no left child. (Is that what you meant?)

Yes, that is exactly what I meant.
0
 
LVL 16

Accepted Solution

by:
imladris earned 400 total points
ID: 9853996
OK, here's a stab at the "replacement" strategy.

You are looking for the largest value of the "70" subtree, right? You're going to find that by starting at 70 and going left until you find NULL (that is, regardless of the value of the rchild pointer).

For this node you found the lchild is guaranteed to be NULL. The rchild may or may not point to something.

If the rchild is NULL, copy the node value up to the "to be deleted" node, NULL the lchild of the node that was pointing to the replacement value (74 in the example tree), and delete the replacement node (i.e. the 74).

If the rchild is *not* NULL (that is, we'll suppose there was a node 73 to the right of the 74 node), then the 74 is still copied up to the "to be deleted" node, but the 73 node must now be "promoted". You can do this by making the lchild of the parent of the replacement node (i.e. 74) point to the rchild node (73) instead. That is, when you're done 74 will be the parent of 80 and 70, and 70 will be the parent of 73 and 68. Whatever children 73 may or may not have will automatically be in the right place.

What do you think?
0
 
LVL 16

Expert Comment

by:imladris
ID: 9853998
P.S. in the rchild *not* NULL case, you still, of course, have to delete the replacement node (the original 74 node) at the end.
0
 
LVL 16

Expert Comment

by:imladris
ID: 9854021
That is, in summary, instead of NULLing the lchild of the parent of the replacement node (i.e. make the lchild of 70 point to NULL), you make it point to the rchild of the replacement node instead.

Or, in general, I suppose, you make the lchild of the parent (70) point to the rchild of the replacment node, which would be NULL in the first case, and the 73 node in the second.
0
 

Author Comment

by:closet
ID: 9858545
Thanks for all the help, and for working it through with me. The things that worked turned out the be assigning the data part of the node  and making the lchild of the parent of the node to delete point to the rchild of the replacement node. Hurray!

Closet
0

Featured Post

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
Problem with MFCApp 78 317
SCANF - LIMIT THE NUMBER OF CHARARACTERS 1 58
how to understand recursion 12 206
List out all word 7 224
An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.

706 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!

Get 1:1 Help Now