// Chap 10 , pp 489 - 493
// Rename this file as BST.cpp

// *********************************************************
// Implementation file BST.cpp.
// *********************************************************
#include "BST.h"     // header file
#include <stddef.h>  // definition of NULL

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

bstClass::bstClass() : Root(NULL)
{
}  // end constructor

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

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

boolean bstClass::SearchTreeIsEmpty()
{
   return boolean(Root == NULL);
}  // end SearchTreeIsEmpty

void bstClass::SearchTreeInsert(treeItemType NewItem,
										  boolean& Success)
{
   InsertItem(Root, NewItem, Success);
}  // end SearchTreeInsert

void bstClass::SearchTreeDelete(keyType SearchKey,
                                boolean& Success)
{
   DeleteItem(Root, SearchKey, Success);
}  // end SearchTreeDelete

void bstClass::SearchTreeRetrieve(keyType SearchKey,
                                  treeItemType& TreeItem,
                                  boolean& Success)
{
   RetrieveItem(Root, SearchKey, TreeItem, Success);
}  // end SearchTreeRetrieve

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

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

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

void bstClass::InsertItem(ptrType& TreePtr, 
                          treeItemType NewItem,
                          boolean& Success)
{
   if (TreePtr == NULL)
   {  // position of insertion found; insert after leaf

      // create a new node
      TreePtr = new treeNode(NewItem, NULL, NULL);

      // was allocation successful?
      Success = boolean(TreePtr != NULL);
   }

   // else search for the insertion position
   else if (NewItem.Key < TreePtr->Item.Key)
      // search the left subtree
      InsertItem(TreePtr->LChildPtr, NewItem, Success);

   else  // search the right subtree
      InsertItem(TreePtr->RChildPtr, NewItem, Success);
}  // end InsertItem

void bstClass::ProcessLeftmost(ptrType& NodePtr,
                               treeItemType& TreeItem)
{
   if ( (NodePtr != NULL) && (NodePtr->LChildPtr == NULL) )
	{  TreeItem = NodePtr->Item;
      ptrType DelPtr = NodePtr;
      NodePtr = NodePtr->RChildPtr;
      DelPtr->RChildPtr = NULL;  // defense
      delete DelPtr;
   }

   else 
      ProcessLeftmost(NodePtr->LChildPtr, TreeItem);
}  // end ProcessLeftmost

void bstClass::DeleteRootItem(ptrType& NodePtr)
// Algorithm note: There are four cases to consider:
//   1. The root is a leaf.
//   2. The root has no left child.
//   3. The root has no right child.
//   4. The root has two children.
// Calls: ProcessLeftmost.
{
   ptrType      DelPtr;
	treeItemType ReplacementItem;

   if (NodePtr != NULL)
   {  // test for a leaf
      if ( (NodePtr->LChildPtr == NULL) &&
           (NodePtr->RChildPtr == NULL) )
      {  delete NodePtr;
         NodePtr = NULL;
      }  // end if leaf

      // test for no left child
      else if (NodePtr->LChildPtr == NULL)
      {  DelPtr = NodePtr;
         NodePtr = NodePtr->RChildPtr;
         DelPtr->RChildPtr = NULL;
         delete DelPtr;
      }  // end if no left child

      // test for no right child
      else if (NodePtr->RChildPtr == NULL)
		{  DelPtr = NodePtr;
         NodePtr = NodePtr->LChildPtr;
         DelPtr->LChildPtr = NULL;
         delete DelPtr;
      }  // end if no right child

      // there are two children:
      // delete and retrieve the inorder successor
      else
      {  ProcessLeftmost(NodePtr->RChildPtr, 
                                           ReplacementItem);
         NodePtr->Item = ReplacementItem;
      }  // end if two children
   }  // end if NodePtr != NULL
}  // end DeleteRootItem

void bstClass::DeleteItem(ptrType& TreePtr,
                          keyType SearchKey,
                          boolean& Success)
// Calls: DeleteRootItem.
{
   if (TreePtr == NULL)
      Success = FALSE;  // empty tree

   else if (SearchKey == TreePtr->Item.Key)
   {  // item is in the root of some subtree
      DeleteRootItem(TreePtr);  // delete the item
      Success = TRUE;
   }  // end if in root

   // else search for the item
   else if (SearchKey < TreePtr->Item.Key)
      // search the left subtree
      DeleteItem(TreePtr->LChildPtr, SearchKey, Success);

   else  // search the right subtree
      DeleteItem(TreePtr->RChildPtr, SearchKey, Success);
}  // end DeleteItem

void bstClass::RetrieveItem(ptrType TreePtr,
									 keyType SearchKey,
                            treeItemType& TreeItem,
                            boolean& Success)
{
   if (TreePtr == NULL)
      Success = FALSE;  // empty tree

   else if (SearchKey == TreePtr->Item.Key)
   {  // item is in the root of some subtree
      TreeItem = TreePtr->Item;
      Success = TRUE;
   }

   else if (SearchKey < TreePtr->Item.Key)
   // search the left subtree
      RetrieveItem(TreePtr->LChildPtr, SearchKey, TreeItem,
                                                   Success);

   else  // search the right subtree
      RetrieveItem(TreePtr->RChildPtr, SearchKey, TreeItem,
																	Success);
}  // end RetrieveItem

// Implementations of Preorder, Inorder, Postorder,
// CopyTree, DestroyTree, SetRoot, and Root are the same as
// for the ADT binary tree.
void bstClass::Preorder(ptrType TreePtr,
			functionType Visit)
{
	if (TreePtr != NULL)
	{  Visit(TreePtr->Item);
		Preorder(TreePtr->LChildPtr, Visit);
		Preorder(TreePtr->RChildPtr, Visit);
	} // end if
}  // end Preorder

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

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

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

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

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

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

ptrType bstClass::RootPtr()
{
   return Root;
}  // end RootPtr
// End of implementation file.