//*********************************************
// (Partial) implementation file tree.cc for
// the modified ADT binary tree.
// Pointer-based implementation.
// Programming Project 8
// CS 241 Data Structures
// Fall 2003
//*********************************************
using namespace std;
#include "tree.h"     // header file
#include <fstream>
#include <string>     // definition of NULL
#include <cassert>    // definition of assert

inline int max(int i, int j) 
{
  return (i > j ? i : j);
} // end max

tree::tree() : Root(NULL), treeArraySize(0) 
{
}

tree::tree(const tree& Tree) : treeArraySize(0) 
{
  CopyTree(Tree.Root, Root); // initializes Root
}

tree::~tree() 
{
  DestroyTree(Root);
}

bool tree::BinaryTreeIsEmpty() const 
{
  return Root == NULL;
}

void tree::PreorderTraverse(functionType Visit) 
{
  Preorder(Root, Visit);
}

void tree::InorderTraverse(functionType Visit) 
{
  Inorder(Root, Visit);
}

void tree::PostorderTraverse(functionType Visit) 
{
  Postorder(Root, Visit);
}

tree& tree::operator=(const tree& Rhs) 
{
  if (this != &Rhs) 
  {
    DestroyTree(Root);         // deallocate left-hand side
    CopyTree(Rhs.Root, Root);  // copy right-hand side
  }

  return *this;
}

void tree::CopyTree(treeNode* TreePtr, treeNode*& NewTreePtr) 
{
  // preorder traversal
  if (TreePtr != NULL) 
  { 
    // copy node
    NewTreePtr = new treeNode(TreePtr->Item, NULL, NULL);
    assert(NewTreePtr != NULL);

    CopyTree(TreePtr->LChildPtr, NewTreePtr->LChildPtr);
    CopyTree(TreePtr->RChildPtr, NewTreePtr->RChildPtr);
  } 
  else 
  { 
    // copy empty tree
    NewTreePtr = NULL;
  } 
}

void tree::DestroyTree(treeNode*& TreePtr) 
{
  // postorder traversal
  if (TreePtr != NULL) 
  {
    DestroyTree(TreePtr->LChildPtr);
    DestroyTree(TreePtr->RChildPtr);
    delete TreePtr;
    TreePtr = NULL;
  }
}

void tree::Preorder(treeNode* TreePtr,
		    functionType Visit) 
{
  if (TreePtr != NULL) 
  {
    Visit(TreePtr->Item);
    Preorder(TreePtr->LChildPtr, Visit);
    Preorder(TreePtr->RChildPtr, Visit);
  } 
}

void tree::Inorder(treeNode* TreePtr,
                       functionType Visit) 
{
  if (TreePtr != NULL) 
  {
    Inorder(TreePtr->LChildPtr, Visit);
    Visit(TreePtr->Item);
    Inorder(TreePtr->RChildPtr, Visit);
  } 
} 

void tree::Postorder(treeNode* TreePtr,
                         functionType Visit) 
{
  if (TreePtr != NULL) 
  {
    Postorder(TreePtr->LChildPtr, Visit);
    Postorder(TreePtr->RChildPtr, Visit);
    Visit(TreePtr->Item);
  } 
}