Thread: 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?