#include "BinaryTree.h"
template <class Object>
BinaryNode<Object>::
BinaryNode( const Object & theElement,
BinaryNode *lt, BinaryNode *rt )
: element( theElement ), left( lt ), right( rt )
{
}
template <class Object>
int BinaryNode<Object>::
size( BinaryNode<Object> * t )
{
if( t == NULL )
return 0;
else
return 1 + size( t->left ) + size( t->right );
}
#define max MAX
template <class Comparable>
Comparable max( const Comparable & a, const Comparable & b )
{
return a > b ? a : b;
}
template <class Object>
int BinaryNode<Object>::
height( BinaryNode<Object> * t )
{
if( t == NULL )
return -1;
else
return 1 + max( height( t->left ), height( t->right ) );
}
#undef max
template <class Object>
void BinaryNode<Object>::
printPreOrder( ) const
{
cout << element << endl; if( left != NULL )
left->printPreOrder( ); if( right != NULL )
right->printPreOrder( ); }
template <class Object>
void BinaryNode<Object>::
printPostOrder( ) const
{
if( left != NULL ) left->printPostOrder( );
if( right != NULL ) right->printPostOrder( );
cout << element << endl; }
template <class Object>
void BinaryNode<Object>::
printInOrder( ) const
{
if( left != NULL ) left->printInOrder( );
cout << element << endl; if( right != NULL )
right->printInOrder( ); }
template <class Object>
BinaryNode<Object> * BinaryNode<Object>::
duplicate( ) const
{
BinaryNode<Object> *root =
new BinaryNode<Object>( element );
if( left != NULL ) root->left = left->duplicate( ); if( right != NULL ) root->right = right->duplicate( );
return root; }
template <class Object>
const BinaryTree<Object> &
BinaryTree<Object>::
operator= ( const BinaryTree<Object> & rhs )
{
if( this != &rhs )
{
makeEmpty( );
if( rhs.root != NULL )
root = rhs.root->duplicate( );
}
return *this;
}
template <class Object>
void BinaryTree<Object>::
merge( const Object & rootItem,
BinaryTree<Object> & t1, BinaryTree<Object> & t2 )
{
if( t1.root == t2.root && t1.root != NULL )
{
cerr << "Cannot merge a tree with itself; merge aborted." << endl;
return;
}
Node *oldRoot = root;
root = new Node( rootItem, t1.root, t2.root );
if( this != &t1 && this != &t2 )
makeEmpty( oldRoot );
if( this != &t1 )
t1.root = NULL;
if( this != &t2 )
t2.root = NULL;
}
template <class Object>
void BinaryTree<Object>::
makeEmpty( BinaryNode<Object> * & t )
{
if( t != NULL )
{
makeEmpty( t->left );
makeEmpty( t->right );
delete t;
t = NULL;
}
}