Essential C++

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