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?