6.4 Implementing the Template Class

Each time we insert a new value, we must create a BTnode object, initialize it, and link it somewhere within the tree. We manage the allocation and deallocation of each node explicitly using the new and delete expressions.

insert(), for example, allocates a new BTnode from the program's free store if _root is unset; otherwise, it calls the BTnode insert_value() method to insert the new value into the tree:

template <typename elemType> 


inline void 


BinaryTree<elemType>:: 


insert( const elemType &elem ) 


{ 


    if ( ! _root ) 


           _root = new BTnode<elemType>( elem ); 


    else _root->insert_value( elem ); 


} 

There are two steps to the operation of the new expression. (1) Memory is requested of the program's free store. If sufficient memory is available, a pointer to the object is returned. (If sufficient memory is not available, a bad_alloc exception is raised. We discuss the C++ exception handling facility in Chapter 7.) (2) If the first step succeeds and an initial value is specified, the object is appropriately initialized. For a class type, as in

_root = new BTnode<elemType>( elem ); 

elem is passed to the BTnode constructor. If the allocation step fails, the initialization step is not carried out.

insert_value() is invoked only if a root node is present. The root's left subtree holds values that are less than its value, and the right subtree holds values that are greater. insert_value() recursively invokes itself through either the left or the right child until it finds an unset child to which to attach itself or finds the value already entered. Only one instance of each value is stored in the tree. The BTnode _cnt data member keeps an insertion count. Here is the implementation:

template <typename valType> 


void BTnode<valType>:: 


insert_value( const valType &val ) 


{ 


    if ( val == _val ) 


       { _cnt++; return; } 





    if ( val < _val ) 


    { 


         if ( ! _lchild ) 


              _lchild = new BTnode( val ); 


         else _lchild->insert_value( val ); 


    } 


    else 


    { 


         if ( ! _rchild ) 


              _rchild = new BTnode( val ); 


         else _rchild->insert_value( val ); 


    } 


} 

The removal of a value is complicated by the need to preserve the order of the tree. The general algorithm is to replace the node with its right child. The left child is then reattached as the leaf node of the right child's left subtree. If there is no right child, the node is replaced with the left child. To simplify the implementation, I've treated the removal of the root node as a special case.

template <typename elemType> 


inline void 


BinaryTree<elemType>:: 


remove( const elemType &elem ) 


{ 


    if ( _root ) 


    { 


         if ( _root->_val == elem ) 


              remove_root(); 


         else 


              _root->remove_value( elem, _root ); 


    } 


} 

Both remove_root() and remove_value() reattach the left child as the leaf node of the right child's left subtree. I've factored this operation out into lchild_leaf(), a static member function of the BTnode class:

template <typename valType> 


void BTnode<valType>:: 


lchild_leaf( BTnode *leaf, BTnode *subtree ) 


{ 


    while ( subtree->_lchild ) 


            subtree = subtree->_lchild; 


    subtree->_lchild = leaf; 


} 

remove_root() resets the root node to one of its children, if a child node is present. If the right child is present, it becomes the new root node; the left child, if present, is reattached either directly or through a call of lchild_leaf(). If the right child is null, _root is set to the left child.

template <typename elemType> 


void BinaryTree<elemType>:: 


remove_root() 


{ 


    if ( ! _root ) return; 





    BTnode<elemType> *tmp = _root; 


    if ( _root->_rchild ) 


    { 


        _root = _root->_rchild; 





        // ok, now we must reattach the left child to the 


        // bottom of the right child's left subtree 


        if ( tmp->_lchild ) 


        { 


             // factor out just for readability 


             BTnode<elemType> *lc = tmp->_lchild; 


             BTnode<elemType> *newlc = _root->_lchild; 


             if ( ! newlc ) 


                   // no subtree, let's directly attach it 


                  _root->_lchild = lc; 





             // lchild_leaf() will travel the left subtree 


             // looking for a null left child to attach ... 


             // lchild_leaf is a static member function 


             else BTnode<elemType>::lchild_leaf( lc, newlc ); 


        } 


    } 


    else _root = _root->_lchild; 





    delete tmp; // ok: now we remove the node previously root 


} 

remove_value() takes two parameters: the value to be deleted, if present, and a pointer to the parent node of the node currently under examination.

template <typename valType> 


void BTnode<valType>:: 


remove_value( const valType &val, BTnode *& prev ); 

remove_value()'s parameter list illustrates the two uses of a reference parameter. val is passed as a reference to prevent a potentially expensive copy by value if valType is specified as a class type. Because we don't intend to change val, we pass it as a const.

The second reference parameter is a bit less intuitive. Why are we passing prev as a reference to pointer? Isn't a pointer sufficient? No. Passing a pointer as a parameter allows us to change the object addressed by the pointer but not the address to which the pointer is set. To change the pointer's actual address value, we must add another level of indirection. By declaring prev as a reference to a pointer, we can change both its address value and the value of the object it addresses.

template <typename valType> 


void BTnode<valType>:: 


remove_value( const valType &val, BTnode *& prev ) 


{ 


    if ( val < _val ) 


    { 


         if ( ! _lchild ) 


              return;  // not present 


         else _lchild->remove_value( val, _lchild ); 


    } 


    else 


    if ( val > _val ) 


    { 


         if ( ! _rchild ) 


              return;  // not present 


         else _rchild->remove_value( val, _rchild ); 


    } 


    else 


    { 


      // ok: found it; 


      // reset the tree then delete this node 





      if ( _rchild ) 


      { 


         prev = _rchild; 


         if ( _lchild ) 


           if ( ! prev->_lchild ) 


                  prev->_lchild = _lchild; 


           else BTnode<valType>::lchild_leaf(_lchild,prev->_lchild); 


      } 


      else prev = _lchild; 


      delete this; 


    } 


} 

We also need a function to remove the entire tree. clear() is implemented as a pair of functions: an inline public function and an overloaded private instance that does the real work.

template <typename elemType> 


class BinaryTree { 


public: 


   void clear(){ if ( _root ){ clear( _root ); _root = 0; }} 


   // ... 


private: 


  void clear( BTnode<elemType>* ); 


  // ... 


}; 





template <typename elemType> 


void BinaryTree<elemType>:: 


clear( BTnode<elemType> *pt ) 


{ 


   if ( pt ){ 


       clear( pt->_lchild ); 


       clear( pt->_rchild ); 


       delete pt; 


    } 


} 

The following program builds the binary tree illustrated in Figure 6.1. A preorder display of the tree is generated in three instances: after the tree is built, after the root node is removed, and after an internal node is removed.

#include "BinaryTree.h" 


#include <iostream> 


#include <string> 


using namespace std; 





int main() 


{ 


    BinaryTree<string> bt; 





    bt.insert( "Piglet" ); 


    bt.insert( "Eeyore" ); 


    bt.insert( "Roo" ); 


    bt.insert( "Tigger" ); 


    bt.insert( "Chris" ); 


    bt.insert( "Pooh" ); 


    bt.insert( "Kanga" ); 





    cout << "Preorder traversal: \n"; 


    bt.preorder(); 





    bt.remove( "Piglet" ); 


    cout << "\n\nPreorder traversal after Piglet removal: \n"; 


    bt.preorder(); 





    bt.remove( "Eeyore" ); 





    cout << "\n\nPreorder traversal after Eeyore removal: \n"; 


    bt.preorder(); 





    return 0; 


} 

When compiled and executed, the program generates the following output:

Preorder traversal: 


Piglet  Eeyore  Chris  Kanga  Roo  Pooh  Tigger 





Preorder traversal after Piglet removal: 


Roo  Pooh  Eeyore  Chris  Kanga  Tigger 





Preorder traversal after Eeyore removal: 


Roo  Pooh  Kanga  Chris  Tigger 

Each of the three traversal algorithms ?preorder(), inorder(), and postorder() ?performs an operation on the current node (in our case, it displays _val) and recursively calls itself on the left and right child. The only difference between the three algorithms is the order in which these actions are carried out:

template <typename valType> 


void BTnode<valType>:: 


preorder( BTnode *pt, ostream &os ) const 


{ 


   if ( pt ) 


   { 


        display_val( pt, os ); 


        if ( pt->_lchild ) preorder( pt->_lchild, os ); 


        if ( pt->_rchild ) preorder( pt->_rchild, os ); 


   } 


} 





template <typename valType> 


void BTnode<valType>:: 


inorder( BTnode *pt, ostream &os ) const 


{ 


   if ( pt ) 


   { 


        if ( pt->_lchild ) inorder( pt->_lchild, os ); 


        display_val( pt, os ); 


        if ( pt->_rchild ) inorder( pt->_rchild, os ); 


   } 


} 





template <typename valType> 


void BTnode<valType>:: 


postorder( BTnode *pt, ostream &os ) const 


{ 


   if ( pt ){ 


        if ( pt->_lchild ) postorder( pt->_lchild, os ); 


        if ( pt->_rchild ) postorder( pt->_rchild, os ); 


        display_val( pt, os ); 


   } 


}