Thread: BST delete again, but this time I think I'm close

  1. #1
    Registered User
    Join Date
    Nov 2006
    Posts
    34

    BST delete again, but this time I think I'm close

    I've completely started from the beginning and am trying to get this BST to delete a node. It says that the item isn't found when trying to delete. SO, I'm back to the same trick as before... PLEASE someone tell me what I'm doing wrong?

    There are 2 functions that work together to delete. Here they are specifically:

    Code:
    template< typename NODETYPE >
    void Tree< NODETYPE >::deleteFromTree(TreeNode<NODETYPE>* &ptr)
    {
    	TreeNode <NODETYPE> *current;  //pointer to traverse the tree
    	TreeNode <NODETYPE> *trailCurrent;  //pointer behind current
    	TreeNode <NODETYPE> *temp;
    
    	if(ptr == NULL)
    		cerr<<"Error:  The node to be deleted is NULL.";
    		cout << endl;
    	if(ptr->leftPtr == NULL && ptr->rightPtr == NULL)
    	{
    		temp = ptr;
    		ptr = NULL;
    		delete temp;
    	}
    	if(ptr->leftPtr == NULL)
    	{
    		temp = ptr;
    		ptr = temp->rightPtr;
    		delete temp;
    	}
    	if(ptr->rightPtr == NULL)
    	{
    		temp = ptr;
    		ptr = temp->leftPtr;
    		delete temp;
    	}
    	else
    	{
    		current = ptr->leftPtr;
    		trailCurrent = NULL;
    		while(current->rightPtr != NULL)
    		{
    			trailCurrent = current;
    			current = current->rightPtr;
    		}//end while
    
    		ptr->data = current->data;
    		if(trailCurrent == NULL)  //current did not move;
    			ptr->leftPtr = current->leftPtr;
    		else 
    			trailCurrent->rightPtr = current->leftPtr;
    		delete current;
    	}//end else
    	
    } // end function deleteFromTree
    
    //  function to perform delete node
    template< typename NODETYPE >
    void Tree< NODETYPE >::deleteNode(const NODETYPE &deleteValue)
    {
    	TreeNode <NODETYPE> *current;  //pointer to traverse the tree
    	TreeNode <NODETYPE> *trailCurrent;  //pointer behind current
    	bool found = false;
    
    	if(rootPtr == NULL)
    		cerr<<"Error:  The node to be deleted is NULL.";
    	else
    	{
    		current = rootPtr;
    		trailCurrent = rootPtr;
    
    		while(current != NULL && !found)
    		{
    			if(current->data == deleteValue)
    				found = true;
    			else
    			{
    				trailCurrent = current;
    				if(current->data > deleteValue)
    					current =  current->leftPtr;
    				else
    					current = current->rightPtr;
    			}//end else
    		}//end while
    
    		if(current == NULL)
    			cout << "The delete item is not in the list." <<endl;
    		else
    			if(found)
    			{
    				if(current == rootPtr)
    					deleteFromTree(rootPtr);
    				else
    					if(trailCurrent->data > deleteValue)
    						deleteFromTree(trailCurrent->leftPtr);
    					else
    						deleteFromTree(trailCurrent->rightPtr);
    			}//end if
    	}
    }//end deleteNode
    Now here is the entire code with a simple test:

    Code:
    #ifndef TREENODE_H
    #define TREENODE_H
    
    // forward declaration of class Tree
    template< typename NODETYPE > class Tree;  
    
    // TreeNode class-template definition
    template< typename NODETYPE >
    class TreeNode 
    {
       friend class Tree< NODETYPE >;
    public:
       // constructor
       TreeNode( const NODETYPE &d )   
          : leftPtr( 0 ), // pointer to left subtree
            data( d ), // tree node data
            rightPtr( 0 ) // pointer to right substree
       { 
          // empty body 
       } // end TreeNode constructor
    
       // return copy of node's data
       NODETYPE getData() const 
       { 
          return data; 
       } // end getData function
    private:
       TreeNode< NODETYPE > *leftPtr; // pointer to left subtree
       NODETYPE data;
       TreeNode< NODETYPE > *rightPtr; // pointer to right subtree
    }; // end class TreeNode
    
    #endif
    #ifndef TREE_H
    #define TREE_H
    
    #pragma warning(disable: 4786)
    #include <iostream>
    using std::cout;
    using std::endl;
    
    #include <new>
    #include "Treenode.h"
    
    // Tree class-template definition
    template< typename NODETYPE > class Tree
    {
    public:
       Tree(); // constructor
       void insertNode( const NODETYPE & );
       void inOrderTraversal() const;
       void deleteNode(const NODETYPE &);
    private:
       TreeNode< NODETYPE > *rootPtr;
    
       // utility functions
       void insertNodeHelper( TreeNode< NODETYPE > **, const NODETYPE & );
       void inOrderHelper( TreeNode< NODETYPE > * ) const;
       void deleteFromTree(TreeNode<NODETYPE>* &p);
       
    }; // end class Tree
    
    // constructor
    template< typename NODETYPE >
    Tree< NODETYPE >::Tree() 
    { 
       rootPtr = 0; // indicate tree is initially empty 
    } // end Tree constructor
    
    // insert node in Tree
    template< typename NODETYPE >
    void Tree< NODETYPE >::insertNode( const NODETYPE &value )
    { 
       insertNodeHelper( &rootPtr, value ); 
    } // end function insertNode
    
    // utility function called by insertNode; receives a pointer
    // to a pointer so that the function can modify pointer's value
    template< typename NODETYPE >
    void Tree< NODETYPE >::insertNodeHelper( 
       TreeNode< NODETYPE > **ptr, const NODETYPE &value )
    {
       // subtree is empty; create new TreeNode containing value
       if ( *ptr == 0 )  
          *ptr = new TreeNode< NODETYPE >( value );
       else // subtree is not empty
       {
          // data to insert is less than data in current node
          if ( value < ( *ptr )->data )
             insertNodeHelper( &( ( *ptr )->leftPtr ), value );
          else
          {
             // data to insert is greater than data in current node
             if ( value > ( *ptr )->data )
                insertNodeHelper( &( ( *ptr )->rightPtr ), value );
             else // duplicate data value ignored
                cout << value << " dup" << endl;
          } // end else
       } // end else
    } // end function insertNodeHelper
    
    // begin inorder traversal of Tree
    template< typename NODETYPE >
    void Tree< NODETYPE >::inOrderTraversal() const
    { 
       inOrderHelper( rootPtr ); 
    } // end function inOrderTraversal
    
    // utility function to perform inorder traversal of Tree
    template< typename NODETYPE >
    void Tree< NODETYPE >::inOrderHelper(TreeNode< NODETYPE > *ptr ) const
    {
       if ( ptr != 0 ) 
       {
          inOrderHelper( ptr->leftPtr ); // traverse left subtree  
          cout << ptr->data << ' '; // process node                
          inOrderHelper( ptr->rightPtr ); // traverse right subtree
       } // end if
    } // end function inOrderHelper
    
    //  function to perform deleteFromTree
    template< typename NODETYPE >
    void Tree< NODETYPE >::deleteFromTree(TreeNode<NODETYPE>* &ptr)
    {
    	TreeNode <NODETYPE> *current;  //pointer to traverse the tree
    	TreeNode <NODETYPE> *trailCurrent;  //pointer behind current
    	TreeNode <NODETYPE> *temp;
    
    	if(ptr == NULL)
    		cerr<<"Error:  The node to be deleted is NULL.";
    		cout << endl;
    	if(ptr->leftPtr == NULL && ptr->rightPtr == NULL)
    	{
    		temp = ptr;
    		ptr = NULL;
    		delete temp;
    	}
    	if(ptr->leftPtr == NULL)
    	{
    		temp = ptr;
    		ptr = temp->rightPtr;
    		delete temp;
    	}
    	if(ptr->rightPtr == NULL)
    	{
    		temp = ptr;
    		ptr = temp->leftPtr;
    		delete temp;
    	}
    	else
    	{
    		current = ptr->leftPtr;
    		trailCurrent = NULL;
    		while(current->rightPtr != NULL)
    		{
    			trailCurrent = current;
    			current = current->rightPtr;
    		}//end while
    
    		ptr->data = current->data;
    		if(trailCurrent == NULL)  //current did not move;
    			ptr->leftPtr = current->leftPtr;
    		else 
    			trailCurrent->rightPtr = current->leftPtr;
    		delete current;
    	}//end else
    	
    } // end function deleteFromTree
    
    //  function to perform delete node
    template< typename NODETYPE >
    void Tree< NODETYPE >::deleteNode(const NODETYPE &deleteValue)
    {
    	TreeNode <NODETYPE> *current;  //pointer to traverse the tree
    	TreeNode <NODETYPE> *trailCurrent;  //pointer behind current
    	bool found = false;
    
    	if(rootPtr == NULL)
    		cerr<<"Error:  The node to be deleted is NULL.";
    	else
    	{
    		current = rootPtr;
    		trailCurrent = rootPtr;
    
    		while(current != NULL && !found)
    		{
    			if(current->data == deleteValue)
    				found = true;
    			else
    			{
    				trailCurrent = current;
    				if(current->data > deleteValue)
    					current =  current->leftPtr;
    				else
    					current = current->rightPtr;
    			}//end else
    		}//end while
    
    		if(current == NULL)
    			cout << "The delete item is not in the list." <<endl;
    		else
    			if(found)
    			{
    				if(current == rootPtr)
    					deleteFromTree(rootPtr);
    				else
    					if(trailCurrent->data > deleteValue)
    						deleteFromTree(trailCurrent->leftPtr);
    					else
    						deleteFromTree(trailCurrent->rightPtr);
    			}//end if
    	}
    }//end deleteNode
    #endif
    #include "Tree.h" // Tree class definition
    
    int main()
    {
       Tree< string > stringTree; // create Tree of int values
       string stringValue;
       string val;
    
       cout << "Enter 10 string values:\n";
    
       // insert 10 strings to intTree
       for ( int i = 0; i < 10; i++ ) 
       {
          cin >> stringValue;
          stringTree.insertNode( stringValue );
       } // end for
    
       cout << "\nInorder traversal\n";
       stringTree.inOrderTraversal();
    
       cout << "\nDelete a string: \n";
       getline(cin, stringValue);
       stringTree.deleteNode(val);
    
       stringTree.inOrderTraversal();
    
       cout << endl;
       return 0;
    } // end main
    I tried to get the delete right, and I'm stumbling somehow. Those that looked at my last program were helpful telling me that my delete function didn't have any sort of search. I think I've fixed that now, and also prepared for some other things I will have to do with the file later. I've spent literaly days working on this project. This will be my 4th rewrite. I want to learn what it is I'm doing so I won't do it again. I've had the same problem with each consecutive rewrite. The delete function never works!

    Any ideas?

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    In deleteFromTree you need braces around the test for NULL, and several of your if's need to be else if's.
    My best code is written with the delete key.

  3. #3
    Registered User
    Join Date
    Nov 2006
    Posts
    34
    ok, I did that. Still doesn't work. Here is the changes:

    Code:
    template< typename NODETYPE >
    void Tree< NODETYPE >::deleteFromTree(TreeNode<NODETYPE>* &ptr)
    {
    	TreeNode <NODETYPE> *current;  //pointer to traverse the tree
    	TreeNode <NODETYPE> *trailCurrent;  //pointer behind current
    	TreeNode <NODETYPE> *temp;
    
    	if(ptr == NULL)
    	{        //was this here you wanted me to add the braces?
    		cerr<<"Error:  The node to be deleted is NULL.";
    		cout << endl;
    	}
    	else if(ptr->leftPtr == NULL && ptr->rightPtr == NULL)
    	{
    		temp = ptr;
    		ptr = NULL;
    		delete temp;
    	}
    	else if(ptr->leftPtr == NULL)
    	{
    		temp = ptr;
    		ptr = temp->rightPtr;
    		delete temp;
    	}
    	else if(ptr->rightPtr == NULL)
    	{
    		temp = ptr;
    		ptr = temp->leftPtr;
    		delete temp;
    	}
    	else
    	{
    		current = ptr->leftPtr;
    		trailCurrent = NULL;
    		while(current->rightPtr != NULL)
    		{
    			trailCurrent = current;
    			current = current->rightPtr;
    		}//end while
    
    		ptr->data = current->data;
    		if(trailCurrent == NULL)  //current did not move;
    		{
    			ptr->leftPtr = current->leftPtr;
    		}
    		else 
    		{
    			trailCurrent->rightPtr = current->leftPtr;
    		}
    		delete current;
    	}//end else
    	
    } // end function deleteFromTree
    thank you for looking at this. I've learned quite a bit, but not enough, apparantly.

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >Still doesn't work.
    How? What cases fail?
    My best code is written with the delete key.

  5. #5
    Registered User
    Join Date
    Nov 2006
    Posts
    34
    well, its still doing the same thing. It says that the item doesn't exist, and nothing gets deleted. So, I'm working on other parts of this applicaiton. I know there is something simple missing, but I've gone over the logic several times, looking at each case, and it just seems like it should work. Did you compile it and get it to work?

    I've changed the application quite a bit now, its becomming an address book. I've been testing that one independently from my entire application just by using the test I included above.

  6. #6
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >Did you compile it and get it to work?
    Yes. And a cursory look at the algorithm shows nothing untoward. Show me how you're calling these functions. It could be that there's nothing wrong with your tree, but your driver is using it incorrectly.
    My best code is written with the delete key.

  7. #7
    Registered User
    Join Date
    Nov 2006
    Posts
    34
    Its this test code:

    Code:
    #include "Tree.h" // Tree class definition
    
    int main()
    {
       Tree< string > stringTree; // create Tree of int values
       string stringValue;
       string val;
    
       cout << "Enter 10 string values:\n";
    
       
       for ( int i = 0; i < 10; i++ ) 
       {
          cin >> stringValue;
          stringTree.insertNode( stringValue );
       } // end for
    
       cout << "\nInorder traversal\n";
       stringTree.inOrderTraversal();
    
       cout << "\nDelete a string: \n";
       getline(cin, stringValue);
       stringTree.deleteNode(val);
    
       stringTree.inOrderTraversal();
    
       cout << endl;
       return 0;
    } // end main

  8. #8
    Registered User
    Join Date
    Jul 2003
    Posts
    110
    Quote Originally Posted by tms43
    Its this test code:

    Code:
    #include "Tree.h" // Tree class definition
    
    int main()
    {
       Tree< string > stringTree; // create Tree of int values
       string stringValue;
       string val;
    
       cout << "Enter 10 string values:\n";
    
       
       for ( int i = 0; i < 10; i++ ) 
       {
          cin >> stringValue;
          stringTree.insertNode( stringValue );
       } // end for
    
       cout << "\nInorder traversal\n";
       stringTree.inOrderTraversal();
    
       cout << "\nDelete a string: \n";
       getline(cin, stringValue);
       stringTree.deleteNode(val);
    
       stringTree.inOrderTraversal();
    
       cout << endl;
       return 0;
    } // end main
    I am sure that is not what you intended...

  9. #9
    Registered User
    Join Date
    Nov 2006
    Posts
    34
    DOH!

    thanks

  10. #10
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    whoie! Long time no see.
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. BST node deletion help!
    By iunah in forum C Programming
    Replies: 4
    Last Post: 02-01-2009, 05:53 AM
  2. Delete Function in Doubly Linked List
    By Dampecram in forum C Programming
    Replies: 5
    Last Post: 11-15-2008, 04:30 PM
  3. Weird Times I'm getting
    By afflictedd2 in forum Linux Programming
    Replies: 8
    Last Post: 07-23-2008, 07:18 AM
  4. Problem need help
    By Srpurdy in forum C++ Programming
    Replies: 1
    Last Post: 07-24-2002, 12:45 PM
  5. memory management...
    By master5001 in forum Game Programming
    Replies: 24
    Last Post: 01-07-2002, 05:50 PM