#ifndef _BINARYTREE_H_
#define _BINARYTREE_H_
#include <stdlib.h>
template <class Object>
class BinaryTree;
template <class Object>
class BinaryNode
{
public:
BinaryNode( const Object & theElement = Object( ),
BinaryNode *lt = NULL, BinaryNode *rt = NULL );
static int size( BinaryNode *t );
static int height( BinaryNode *t );
void printPreOrder( ) const;
void printPostOrder( ) const;
void printInOrder( ) const;
BinaryNode *duplicate( ) const;
public: Object element;
BinaryNode *left;
BinaryNode *right;
};
template <class Object>
class TreeIterator;
template <class Object>
class BinaryTree
{
public:
BinaryTree( ) : root( NULL ) { }
BinaryTree( const Object & rootItem )
: root( new Node( rootItem ) ) { }
BinaryTree( const BinaryTree & rhs )
: root( NULL ) { *this = rhs; }
~BinaryTree( )
{ makeEmpty( ); }
const BinaryTree & operator= ( const BinaryTree & rhs );
void printPreOrder( ) const
{ if( root != NULL ) root->printPreOrder( ); }
void printInOrder( ) const
{ if( root != NULL ) root->printInOrder( ); }
void printPostOrder( ) const
{ if( root != NULL ) root->printPostOrder( ); }
void makeEmpty( )
{ makeEmpty( root ); }
bool isEmpty( ) const
{ return root == NULL; }
void merge( const Object & rootItem, BinaryTree & t1, BinaryTree & t2 );
int size( ) const
{ return Node::size( root ); }
int height( ) const
{ return Node::height( root ); }
private:
typedef BinaryNode<Object> Node;
Node *root;
friend class TreeIterator<Object>;
void makeEmpty( BinaryNode<Object> * & t );
};
#include "BinaryTree.cpp"
#endif