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! :confused:

Any ideas?

In deleteFromTree you need braces around the test for NULL, and several of your if's need to be else if's.

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.

>Still doesn't work.
How? What cases fail?

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.

>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.

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

---

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...

DOH!

thanks

whoie! Long time no see.