BST delete function

This is a discussion on BST delete function within the C++ Programming forums, part of the General Programming Boards category; Code: void tree1::remove(int coX, int coY) { //Locate the element bool found = false; if(isEmpty()) { cout<<" This Tree is ...

  1. #1
    Registered User
    Join Date
    Jul 2009
    Posts
    38

    BST delete function

    Code:
    void tree1::remove(int coX, int coY)
    {
        //Locate the element
        bool found = false;
        if(isEmpty())
        {
            cout<<" This Tree is empty! "<<endl;
            return;
        }
        tree_node* curr;
        tree_node* parent;
        curr = root;
        while(curr != NULL)
        {
             if(curr->x == coX && curr->y == coY)
             {
                found = true;
                break;
             }
             else
             {
                 parent = curr;
                 if(coX>curr->x) curr = curr->right;
                 else curr = curr->left;
             }
        }
        if(!found)
    		 {
            cout<<" Data not found! "<<endl;
            return;
        }
    
    
    		 // 3 cases :
        // 1. We're removing a leaf node
        // 2. We're removing a node with a single child
        // 3. we're removing a node with 2 children
    
        // Node with single child
        if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL
    && curr->right == NULL))
        {
           if(curr->left == NULL && curr->right != NULL)
           {
               if(parent->left == curr)
               {
                 parent->left = curr->right;
                 delete curr;
               }
               else
               {
                 parent->right = curr->right;
                 delete curr;
               }
           }
           else // left child present, no right child
           {
              if(parent->left == curr)
               {
                 parent->left = curr->left;
                 delete curr;
               }
               else
               {
                 parent->right = curr->left;
                 delete curr;
               }
           }
         return;
        }
    
    		 //We're looking at a leaf node
    		 if( curr->left == NULL && curr->right == NULL)
    		 {
            if(parent->left == curr) parent->left = NULL;
            else parent->right = NULL;
    		 		 delete curr;
    		 		 return;
    		  }
    
    
        //Node with 2 children
        // replace node with smallest value in right subtree
        if (curr->left != NULL && curr->right != NULL)
        {
            tree_node* chkr;
            chkr = curr->right;
            if((chkr->left == NULL) && (chkr->right == NULL))
            {
                curr = chkr;
                delete chkr;
                curr->right = NULL;
            }
            else // right child has children
            {
                //if the node's right child has a left child
                // Move all the way down left to locate smallest element
    
                if((curr->right)->left != NULL)
                {
                    tree_node* lcurr;
                    tree_node* lcurrp;
                    lcurrp = curr->right;
                    lcurr = (curr->right)->left;
                    while(lcurr->left != NULL)
                    {
                       lcurrp = lcurr;
                       lcurr = lcurr->left;
                    }
    		 		 		 		 curr->x = lcurr->x;
    								 curr->y = lcurr->y;
    								 
                    delete lcurr;
                    lcurrp->left = NULL;
               }
               else
               {
                   tree_node* tmp;
                   tmp = curr->right;
                   curr->x = tmp->x;
    			   curr->y = tmp->y;
    		 		 		    curr->right = tmp->right;
                   delete tmp;
               }
    
            }
    		 return;
        }
    
    }
    Above is my function to delete a node from a tree,

    when I run it in Visual Studio I get this error, Run-Time Check Failure #3 - The variable 'parent' is being used without being initialized.

    I been looking at the code and I dont see anything wrong.

    Can some please help me out?

    EDIT:

    I think the issue is when the node to be removed is a root node and it doesnt have any children.

    Hopefully this will be useful

    EDIT:

    I solved the issue
    Last edited by spikestar; 08-31-2010 at 10:02 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ compilation issues
    By Rupan in forum C++ Programming
    Replies: 1
    Last Post: 08-22-2005, 05:45 AM
  2. c++ linking problem for x11
    By kron in forum Linux Programming
    Replies: 1
    Last Post: 11-19-2004, 09:18 AM
  3. Replies: 5
    Last Post: 02-08-2003, 06:42 PM
  4. Interface Question
    By smog890 in forum C Programming
    Replies: 11
    Last Post: 06-03-2002, 05:06 PM
  5. qt help
    By Unregistered in forum Linux Programming
    Replies: 1
    Last Post: 04-20-2002, 09:51 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21