Modifying Binary Search to Find then Delete

Question

I am very new to programming, and I am working with the C++ language. This is for my homework, and is using binary search trees. What I am trying to do is create a function called find_node, which later then calls a function called delete_node. This is what the teacher gave as a prompt for the find_node function.

Prompt from professor:

Add void find_node( const T &val ) method to the class Node to find the node that contains val; if you do not find, there is nothing to do if you find it and p is Node * that points to it, delete p by calling delete_node( Node< T > *&p ).

void delete_node( Node< T > *&p ) method to remove node p from a binary tree

File given by professor

btree.h

#include    <iostream>
#include    "node.h"
//using namespace std;

template < typename elemType >
class BinaryTree {
  public:
BinaryTree( );
~BinaryTree( );
void insert( const elemType & );
void remove( const elemType & );
void inorder( );
bool empty( );
void clear( );

private:
Node< elemType >    *_root;

BinaryTree( const BinaryTree & );
BinaryTree &operator =( const BinaryTree & );
void clear( Node< elemType > * );
};

template < typename elemType >
inline BinaryTree< elemType >::BinaryTree( ) : _root(0)
{
    cout << "BinaryTree::BinaryTree() "
       << "default constructor\n";
}

template < typename elemType >
inline BinaryTree< elemType >::~BinaryTree( )
{
   cout << "BinaryTree::~BinaryTree() destructor\n";
   clear( );
}

template < typename elemType >
inline void BinaryTree< elemType >::clear( )
{
   if( _root )
   {
      clear( _root );
      _root = 0;
   }
}

template < typename elemType >
inline void BinaryTree< elemType >::clear( Node< elemType > *pt )
{
   if( pt ) {
      cout << "clear( ) left of  "  << pt->value( ) << '\n';
      clear( pt->left( ) );
      cout << "clear( ) right of " << pt->value( ) << '\n';
      clear( pt->right( ) );
      delete pt;
    }
}

template < typename elemType >
inline void BinaryTree< elemType >::insert( const elemType &e )
{
   if( !_root )
   {
      _root = new Node< elemType >( e );
   }
   else
   {
      _root->insert_value( e );
   }
}

template < typename elemType >
inline void BinaryTree< elemType >::remove( const elemType &e )
{
  _root->find_node( _root, e );
}

template < typename elemType>
inline void BinaryTree< elemType >::inorder( )
{
   _root->inorder( _root );
   cout << '\n';
}

Given by professor, but is the file I have to add the 2 methods to from the prompt

node.h

#ifndef     NODE_H

#define     NODE_H

#include    <string>

using namespace std;

template< typename T >
class Node
{
  public:
      Node( const T &);

      T  value( )  const;
      T  value( const T & );

      void insert_value( const T & );
      void inorder( const Node * );
      void find_node( const T &val, const T* root );
    //bool find_node( const T &val, Node < T > *node) const;
      void delete_node( Node< T > *&p );

      Node *  left ( ) const;
      Node *  left ( Node * );
      Node *  right( ) const;
      Node *  right( Node * );

   private:
      T       _value;
      Node *  _left;
      Node *  _right;
      Node< T > * root; //point to root node
      Node::Node( const Node & );
      Node &operator =( const Node & );



};


template< typename T >
inline Node< T >::Node( const T &rhs )
{
   _value = rhs;                       // assign rhs to _value
   _left  =  _right = 0;               // node is not part of a tree yet
}


template< typename T >
inline T Node< T >::value( ) const
{
   return _value;
}


template< typename T >
inline T Node< T >::value( const T &rhs )
{
   _value = rhs;                       // new value for _value
   return _value;
}


template< typename T >
inline Node< T > *Node< T >::left( ) const
{
   return _left;
}


template< typename T >
inline Node< T > *Node< T >::left( Node< T > *rhs )
{
   _left = rhs;

   return _left;
}


template< typename T >
inline Node< T > *Node< T >::right( ) const
{
   return _right;
}


template< typename T >
inline Node< T > *Node< T >::right( Node< T > *rhs )
{
   _right = rhs;
   return _right;
}


template< typename T >
inline void Node< T >::insert_value( const T &val )
{
    if( val == _value )
{
    return;                     // value already in the tree
}
if( val < _value )              // val should appear at the left
{
    if( ! _left )               // no left subtree ?
    {                           // add new node here
        _left = new Node( val );
    }
    else                        // try the subtree
    {
        _left->insert_value( val );
    }
}
else                            // val should appear at the right
{
    if( ! _right )              // no right subtree ?
    {                           // add new node here
        _right = new Node( val );
    }
    else                        // try the subtree
    {
        _right->insert_value( val );
    }
  }
}


template< typename T >
inline void Node< T >::inorder( const Node< T > *pt )
{
   if( pt )
   {
      inorder( pt->_left );
      cout << std::hex << pt->_left << std::dec << '\t';
      cout << std::hex << pt << std::dec << '\t';
      cout << std::hex << pt->_right << std::dec << '\t';
      cout << pt->_value << '\n';
      inorder( pt->_right );
   }
}


template <typename T>
Node<T> const * find_node(const T &val)
{
   Node<T> const * curr = root;
   while( curr != 0 )
   {
      if (val == curr -> _value)  {
       break;
    }
    else if (val < curr -> _value) {
        curr = curr -> _left;
    |
    else {
        curr = curr -> _right;
    }
}
return curr;
}
}

template <typename T >
inline void find_node( const T & val, const T * root ) {
Node<T> const * ptrFoundNode = find_node_pointer( val, root );
if( ptrFoundNode ) {
    delete_node( ptrFoundNode, root );
  }
}

template< typename T >
inline void Node< T >::delete_node(Node < T > *&p)
{

Node<T> *curr, *prev, *temp;
   if (p == NULL) return;
   if (p->_left == NULL && p->_right == NULL) {
    // no children - easy
    // *** if allowing counted duplicates:
    // ***    if (p->getCount() > 1) (*p)--;
    // ***    else {
       temp = p;
       p = NULL;
       delete temp;
    }
 else if (p->_left == NULL) {
    // only a right child - still easy
    // *** if allowing counted duplicates:
    // ***    if (p->getCount() > 1) (*p)--;
    // ***    else {
       temp = p;
       p = temp->_right;
       delete temp;
    }
 else if (p->_right == NULL) {
    // only a left child - still easy
    // *** if allowing counted duplicates:
    // ***    if (p->getCount() > 1) (*p)--;
    // ***    else {
       temp = p;
       p = temp->_left;
       delete temp;
    }
 else {
    // two children - this is the hard case
    // use successor: once right, then as far left as possible
    // *** if allowing counted duplicates:
    // ***    if (p->getCount() > 1) (*p)--;
    // ***    else {
       curr = p->_right;
       prev = NULL;
       while (curr->_left != NULL) {
           prev = curr;
           curr = curr->left;
       }
       p->data = curr->data;
       if (prev == NULL) p->_right = curr->_right;
       else prev->_left = curr->_right;

       delete curr;
   }
}


#endif

Answer 1

Following is a sketch with minimum changes to OP's code:

Node<T> const * find_node_pointer( Node<T> const * root, T const & val)
{
    Node<T> const * curr = root;
    while( curr != 0 )
    {
        if (val == curr -> _value)  {
           break;
        }
        else if (val < curr -> _value) {
            curr = curr -> _left;
        |
        else {
            curr = curr -> _right;
        }
    }
    return curr;
}

Caller:

void find_node( Node<T> const * root, T const & val ) {
    Node<T> const * ptrFoundNode = find_node_pointer( root, val );
    if( ptrFoundNode ) {
        delete_node( root, ptrFoundNode );
    }
}