// Chap 10, pp 456 - 462
// Rename this file as BT.cpp

// ********************************************************
// Implementation file BT.cpp for the ADT binary tree.
// ********************************************************
#include "BT.h"      // header file
#include <stddef.h>  // definition of NULL
#include <assert.h>  // for assert()

struct treeNode
{  treeItemType Item;
   ptrType      LChildPtr, RChildPtr;

   // constructor:
   treeNode(treeItemType NodeItem, ptrType L, ptrType R);
};  // end struct

treeNode::treeNode(treeItemType NodeItem, 
                   ptrType L, ptrType R):
   Item(NodeItem), LChildPtr(L), RChildPtr(R)
{
}  // end constructor

binTreeClass::binTreeClass() : Root(NULL)
{
}  // end default constructor

binTreeClass::binTreeClass(treeItemType RootItem)
{
   Root = new treeNode(RootItem, NULL, NULL);
   assert(Root != NULL);
}  // end constructor

binTreeClass::binTreeClass(ptrType NodePtr): 
   Root(NodePtr)
{
}  // end protected constructor

binTreeClass::binTreeClass(treeItemType RootItem, 
                           binTreeClass LeftTree, 
                           binTreeClass RightTree)
{
   boolean Success;

   Root = new treeNode(RootItem, NULL, NULL);
   assert(Root != NULL);

   AttachLeftSubtree(LeftTree, Success);
   if (Success)
      AttachRightSubtree(RightTree, Success);
   assert(Success);
}  // end constructor

binTreeClass::binTreeClass(const binTreeClass& T)
{
   CopyTree(T.Root, Root);
}  // end copy constructor

void binTreeClass::~binTreeClass()
{
   DestroyTree(Root);
}  // end destructor

boolean binTreeClass::BinaryTreeIsEmpty()
{
   return boolean(Root == NULL);
}  // end BinaryTreeIsEmpty

treeItemType binTreeClass::RootData()
{
   assert(Root != NULL);
   return Root->Item;
}  // end RootData

void binTreeClass::SetRootData(treeItemType NewItem)
{
   if (Root != NULL)
      Root->Item = NewItem;
   else
   {  Root = new treeNode(NewItem, NULL, NULL);
      assert(Root != NULL);
   }
}  // end SetRootData

void binTreeClass::AttachLeft(treeItemType NewItem, 
                              boolean& Success)
{
   Success = boolean(!BinaryTreeIsEmpty() &&
		     Root->LChildPtr == NULL);

   if (Success)
   {  // Assertion: nonempty tree and no left child
      Root->LChildPtr = new treeNode(NewItem, NULL, NULL);
      assert(Root->LChildPtr != NULL);
   }
 }  // end AttachLeft

void binTreeClass::AttachRight(treeItemType NewItem,
                               boolean& Success)
{
   Success = boolean(!BinaryTreeIsEmpty() &&
							Root->RChildPtr == NULL);

   if (Success)
   {  // Assertion: nonempty tree and no right child
      Root->RChildPtr = new treeNode(NewItem, NULL, NULL);
      assert(Root->RChildPtr != NULL);
   }
}  // end AttachRight

void binTreeClass::AttachLeftSubtree(binTreeClass LeftTree, 
                                     boolean& Success)
{
   Success = boolean(!BinaryTreeIsEmpty() &&
							Root->LChildPtr == NULL);

   if (Success)
      // Assertion: nonempty tree and no left child
      CopyTree(LeftTree.Root, Root->LChildPtr);
}  // end AttachLeftSubtree

void binTreeClass::AttachRightSubtree(binTreeClass RightTree, 
                                      boolean& Success)
{
   Success = boolean(!BinaryTreeIsEmpty() &&
		     Root->RChildPtr == NULL);

   if (Success)
      // Assertion: nonempty tree and no left child
      CopyTree(RightTree.Root, Root->RChildPtr);
}  // end AttachRightSubtree

void binTreeClass::DetachLeftSubtree(binTreeClass& LeftTree, 
                                     boolean& Success)
{
   Success = boolean(!BinaryTreeIsEmpty());
   if (Success)
   {  CopyTree(Root->LChildPtr, LeftTree.Root);
      DestroyTree(Root->LChildPtr);
   }
}  // end DetachLeftSubtree

void binTreeClass::DetachRightSubtree(binTreeClass& RightTree,
                                      boolean& Success)
{
   Success = boolean(!BinaryTreeIsEmpty());
   if (Success)
   {  CopyTree(Root->RChildPtr, RightTree.Root);
      DestroyTree(Root->RChildPtr);
   }
}  // end DetachRightSubtree

binTreeClass binTreeClass::LeftSubtree()
{
   ptrType SubTreePtr;

   if (BinaryTreeIsEmpty())
      return binTreeClass(NULL);
   else
   {  CopyTree(Root->LChildPtr, SubTreePtr);
      return binTreeClass(SubTreePtr);
   }
}  // end LeftSubtree

binTreeClass binTreeClass::RightSubtree()
{
   ptrType SubTreePtr;

   if (BinaryTreeIsEmpty())
      return binTreeClass(NULL);
   else
   {  CopyTree(Root->RChildPtr, SubTreePtr);
      return binTreeClass(SubTreePtr);
   }
}  // end RightSubtree

void binTreeClass::PreorderTraverse(functionType Visit)
{
   Preorder(Root, Visit);
}  // end PreorderTraverse

void binTreeClass::InorderTraverse(functionType Visit)
{
   Inorder(Root, Visit);
}  // end InorderTraverse

void binTreeClass::PostorderTraverse(functionType Visit)
{
   Postorder(Root, Visit);
}  // end PostorderTraverse

void binTreeClass::operator=(const binTreeClass& T)
{
   CopyTree(T.Root, Root);
}  // end operator=

void binTreeClass::CopyTree(ptrType TreePtr, 
                            ptrType& 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);
   }  // end if
   else
      NewTreePtr = NULL;  // copy empty tree
}  // end CopyTree

void binTreeClass::DestroyTree(ptrType& TreePtr)
{
   // postorder traversal
   if (TreePtr != NULL)
   {  DestroyTree(TreePtr->LChildPtr);
      DestroyTree(TreePtr->RChildPtr);
      delete TreePtr;
      TreePtr = NULL;
   }  // end if
}  // end DestroyTree

void binTreeClass::SetRootPtr(ptrType NewRoot)
{
   Root = NewRoot;
}  // end SetRoot

ptrType binTreeClass::RootPtr()
{
   return Root;
}  // end RootPtr

void binTreeClass::Preorder(ptrType TreePtr,
                            functionType Visit)
{
   if (TreePtr != NULL)
   {  Visit(TreePtr->Item);
      Preorder(TreePtr->LChildPtr, Visit);
      Preorder(TreePtr->RChildPtr, Visit);
   } // end if
}  // end Preorder

void binTreeClass::Inorder(ptrType TreePtr,
                           functionType Visit)
{
   if (TreePtr != NULL)
   {  Inorder(TreePtr->LChildPtr, Visit);
      Visit(TreePtr->Item);
      Inorder(TreePtr->RChildPtr, Visit);
   } // end if
}  // end Inorder

void binTreeClass::Postorder(ptrType TreePtr,
                             functionType Visit)
{
   if (TreePtr != NULL)
   {  Postorder(TreePtr->LChildPtr, Visit);
      Postorder(TreePtr->RChildPtr, Visit);
      Visit(TreePtr->Item);
   } // end if
}  // end Postorder
// End of implementation file.