//
//  ============================================================
//
//              	BinaryTree
//
//  ============================================================
//
//
//      Copyright (C) 1992,1993,1994,1995,1996
//
//                      Professor Kenneth I. Joy
//                      Computer Science Department
//                      University of California
//                      Davis, CA  95616
//
//      Permission is granted to use at your own risk and
//      distribute this software in source and binary forms
//      provided the above copyright notice and this paragraph
//      are preserved on all copies.  This software is provided
//      "as is" with no express or implied warranty.
//
//
//  ============================================================
//


#include <stdlib.h>
#include <math.h>
#include <stream.h>
#include <strings.h>

#include "BinaryTree.h"

#define		TRUE		1 
#define		FALSE		0


/*
   ============================================================

		  CONSTRUCTOR, DESTRUCTOR

   ============================================================
*/

BinaryTree :: BinaryTree ()

   {
      _value = -100000.0 ;
      _left_child = NULL ;
      _right_child = NULL ;
   }

BinaryTree :: BinaryTree ( const double val,
			   BinaryTree *left, BinaryTree *right ) 

   {
      _value = val ;
      _left_child = left ;
      _right_child = right ;
   }


BinaryTree :: BinaryTree ( const BinaryTree& t )

   {
      _value = t._value ;
      _left_child = _Copy ( t._left_child ) ;
      _right_child = _Copy ( t._right_child ) ;
   }


BinaryTree :: ~BinaryTree () 

   {
      if ( _left_child != NULL ) delete _left_child ;
      if ( _right_child != NULL ) delete _right_child ;
   }

/*
   ============================================================

		  OPERATOR=

   ============================================================
*/

BinaryTree& BinaryTree :: operator= ( const BinaryTree& t )

   {
      if ( &t == this ) return ( *this ) ;

      _value = t._value ;
      _left_child = _Copy ( t._left_child ) ;
      _right_child = _Copy ( t._right_child ) ;

      return ( *this ) ;
   }

/*
   =============================================================

	       OUTPUT

   =============================================================
*/

ostream& operator<< ( ostream& co, const BinaryTree& t ) 

   {
      co << " " << t._value ;

      if ( t._left_child != NULL ) 
	 co << t._left_child ;

      if ( t._right_child != NULL ) 
	 co << t._right_child ;

      return co ;
   }

ostream& operator<< ( ostream& co, const BinaryTree *t )

   {
      co << *t ;
      return ( co ) ;
   }


/*
   ============================================================

		  COMPARISON

   ============================================================
*/

int operator== ( const BinaryTree& t1, const BinaryTree& t2 )

   {
      if ( t1.value() != t2.value() ) return ( FALSE ) ;

      if ( ( t1.left_child() == NULL ) &&
           ( t2.left_child() != NULL ) )
	 return ( FALSE ) ;

      if ( ( t1.left_child() != NULL ) &&
           ( t2.left_child() == NULL ) )
	 return ( FALSE ) ;

      if ( ( t1.left_child() != NULL ) &&
           ( t2.left_child() != NULL ) ) {
	 if ( *(t1.left_child()) != *(t2.left_child()) ) 
	    return ( FALSE ) ;
	 }

      if ( ( t1.right_child() == NULL ) &&
           ( t2.right_child() != NULL ) )
	 return ( FALSE ) ;

      if ( ( t1.right_child() != NULL ) &&
           ( t2.right_child() == NULL ) )
	 return ( FALSE ) ;

      if ( ( t1.right_child() != NULL ) &&
           ( t2.right_child() != NULL ) ) {
	 if ( *(t1.right_child()) != *(t2.right_child()) ) 
	    return ( FALSE ) ;
	 }

      return ( TRUE ) ;
   }

int operator!= ( const BinaryTree& t1, const BinaryTree& t2 )

   {
      return ( ! ( t1 == t2 ) ) ;
   }

/*
   ============================================================

		  ADD

   ============================================================
*/

void BinaryTree :: add ( const double val )

   {
		//  First compare against the root to see 
		//     If this should be placed in the left 
		//     subtree, or the right subtree.

      if ( val < _value ) {

	    if ( _left_child != NULL ) {

			//  Add to the left subtree

		  _left_child -> add ( val ) ;
		  }
	       else {

			//  Create a new tree node as the left subtree

		  BinaryTree *t = new BinaryTree ( val, NULL, NULL ) ;
		  _left_child = t ;
		  }
	    }
	 else {

	    if ( _right_child != NULL ) {

			//  Add to the right subtree

		  _right_child -> add ( val ) ;
		  }
	       else {

			//  Create a new tree node as the right subtree

		  BinaryTree *t = new BinaryTree ( val, NULL, NULL ) ;
		  _right_child = t ;
		  }
	    }
	 
   }


/*
   ============================================================

		  INORDER

   ============================================================
*/

void BinaryTree :: inorder () const

   {
      if ( _left_child != NULL ) _left_child -> inorder() ;

      cout << " " << _value ;

      if ( _right_child != NULL ) _right_child -> inorder() ;
   }


/*
   ============================================================

		  PREORDER

   ============================================================
*/

void BinaryTree :: preorder () const

   {
      cout << " " << _value ;

      if ( _left_child != NULL ) _left_child -> preorder() ;

      if ( _right_child != NULL ) _right_child -> preorder() ;
   }


/*
   ============================================================

		  POSTORDER

   ============================================================
*/

void BinaryTree :: postorder () const

   {
      if ( _left_child != NULL ) _left_child -> postorder() ;

      if ( _right_child != NULL ) _right_child -> postorder() ;

      cout << " " << _value ;
   }


/*
   ============================================================

		  COPY

   ============================================================
*/

BinaryTree * _Copy ( BinaryTree * t ) 

   {
      if ( t == NULL ) return ( NULL ) ;

      BinaryTree *root = new BinaryTree 
				( t -> value(), 
				  _Copy ( t -> left_child() ),
				  _Copy ( t -> right_child() ) ) ;

      return ( root ) ;
   }