plusplus]
#include <cstdlib> //Provides EXIT_SUCCESS
#include <iostream> //Provides cout, cin
#include <string> //Provides string class
 
using namespace std;
 
 
template <class Item>
 
class binary_tree_node
{
public:
 
    //TYPEDEF
    typedef Item value_type;
 
    //CONSTRUCTOR
    binary_tree_node(
        const Item& init_data = Item(),
        binary_tree_node* init_left = NULL,
        binary_tree_node* init_right = NULL
        )
    {
        data_field = init_data;
        left_field = init_left;
        right_field = init_right;
    }
 
    //MODIFICATION MEMBER FUNCTIONS
 
    Item& data() { return data_field; }
    binary_tree_node*& left() { return left_field; }
    binary_tree_node*& right() { return right_field; }
    void set_data(const Item& new_data) { data_field = new_data; }
    void set_left(binary_tree_node* new_left) { left_field = new_left; }
    void set_right(binary_tree_node* new_right) { right_field = new_right; }
 
    //CONSTANT MEMBER FUNCTIONS
    const Item& data() const { return data_field; }
    const binary_tree_node* left() const { return left_field; }
    const binary_tree_node* right() const { return right_field; }
    bool is_leaf() const
    { return (left_field ==NULL) && (right_field ==NULL); }
 
private:
    Item data_field;
    binary_tree_node *left_field;
    binary_tree_node *right_field;
};
 
 
template <class Item>
void tree_clear(binary_tree_node<Item>*& root_ptr);
//Precondition: root_ptr is the root pointer of a binary tree (whihc may be NULL for the empty tree
//Postcondition: All nodes at the root or below have been returned to the heap, and root_ptr has been set to NULL.
 
template <class Item>
binary_tree_node<Item>* tree_copy
                        (const binary_tree_node<Item>* root_ptr);
//Precondition: root_ptr is the root pointer of a binary tree (which may be NULL for the empty tree).
//Postcondition: A copy of the binary tree has been made, and the return value is apointer to the root of this copy.
 
template <class Item>
void tree_clear(binary_tree_node<Item>*& root_ptr)
{
    if (root_ptr != NULL)
    {
        tree_clear( root_ptr->left());
        tree_clear( root_ptr->right());
        delete root_ptr;
        root_ptr = NULL;
    }
}
 
 
template <class Item>
binary_tree_node<Item>* tree_copy
                        (const binary_tree_node<Item>* root_ptr)
{
    binary_tree_node<Item> *l_ptr;
    binary_tree_node<Item> *r_ptr;
 
    if (root_ptr ==NULL)
        return NULL;
    else
    {
        l_ptr = tree_copy( root_ptr->left());
        r_ptr = tree_copy( root_ptr->right());
        return new binary_tree_node<Item>
            (root_ptr->data(), l_ptr, r_ptr);
    }
}