//********************************************************************************
// C++ Certificate Program Intermediate Spring 1999 : Stephen Philips
//
// Final Project
// File       : \\Venus\katy\C++ Certificate\intermediate\Final Project
//				\BinaryTree.cpp
//
// Purpose    : Implementation for class BinaryTree using in-order transversal.
//
// Author     : Hsin-yi F. Berg
// Date		  : 6/2/99
// Update	  : 6/7/99
//********************************************************************************

#include "BinaryTree.h"
#include <string.h>
#include <assert.h>

/*
	BinaryTree::BinaryTree()

	Default constructor for a BinaryTree.
	A BinaryTree is created empty.
*/

BinaryTree::BinaryTree():root(NULL), size(0)

{}

/*
	BinaryTree::~BinaryTree()

	Destructor for a BinaryTree.
*/

BinaryTree::~BinaryTree()

{
	delete root;
}

/*
void BinaryTree::Destroy(LeafNode *&rpLeafNode)

{
	// this recursive function will trasverse the whole binary
	// tree from top to the node with no branch (no left and no
	// right) and delete that node on the way of returning,
	// repeat this process all the way back to the top.

	if(rpLeafNode == NULL)
		return;

	// find the left most LeafNode until hit NULL.
	Destroy(rpLeafNode->GetLeft());
	// when there is no more left LeafNode, go to the right subtree.
	// and find the left most LeafNode of that subtree.
	Destroy(rpLeafNode->GetRight());

	// when we get to this point, pLeafNode is the node that has no
	// left and no right LeafNode, so we can just delete it.
	delete rpLeafNode;
	size--;
	// setting pLeafNode to NULL is important because LeafNode only
	// delete the key pointer, it assumes that left and right are NULL
	rpLeafNode = NULL;
}
*/

/*
void BinaryTree::Add(KEY word)
{
	// call InsertLeafNode, which recursively find the
	// correct poistion and insert the newLeafNode.
	InsertLeafNode(&root, word);	// pass the reference of root
}

void BinaryTree::InsertLeafNode(LeafNode **ppLeafNode, KEY word)
{
	// if we find the position to add the newLeafNode.
	if(*ppLeafNode == NULL) {
		*ppLeafNode = new LeafNode(word);
		assert(*ppLeafNode);
		size--;
	}

	// if the word is already in the tree, just increment the value field in that LeafNode.
	else if(strcmp((*ppLeafNode)->GetKey(), word) == 0) {
		(*ppLeafNode)->IncrementValue();
	}

	// if the key is smaller, search left subtree for the insert position.
	else if(smaller((*ppLeafNode)->GetKey(), word))
		//ppLeafNode->AddLeft(word);
		InsertLeafNode( &((*ppLeafNode)->GetLeft()), word);
	// otherwise, search right subtree for the insert position.

	else
		InsertLeafNode( &((*ppLeafNode)->GetRight()), word);
}
*/

/*
	void BinaryTree::Add(KEY word)

	Add an item to the tree.
*/
void BinaryTree::Add(KEY word)
{
	if( root != NULL )
		InsertLeafNode(root, word);
	else {
		root = new LeafNode(word);
		size++;
	}
}

/*
	void BinaryTree::InsertLeafNode(LeafNode *pLinkNode, KEY word)

	Add the item to the left if its key is smaller, otherwise to the right.
	used in Add function.
*/
void BinaryTree::InsertLeafNode(LeafNode *pLeafNode, KEY word)
{
	int iResult = strcmp(word, pLeafNode->GetKey());

	if(iResult == 0)
	{
		pLeafNode->IncrementValue();
	}
	else if(iResult < 0)
	{
		if(pLeafNode->GetLeft() == NULL) {
			pLeafNode->AddLeft(word);
			size++;
		}
		else
			InsertLeafNode(pLeafNode->GetLeft(), word);
	}
	else
	{
		if(pLeafNode->GetRight() == NULL) {
			pLeafNode->AddRight(word);
			size++;
		}
		else
			InsertLeafNode(pLeafNode->GetRight(), word);
	}
}

/*
	bool BinaryTree::smaller(KEY word1, KEY word2)

	Comparison function for AddHelper.
	Return true is key1 is smaller than key2
*/
bool BinaryTree::smaller(KEY word1, KEY word2)
{
	return (strcmp(word1, word2) < 0);
}

/*
	void BinaryTree::Delete(KEY word)

	Delete an item from the tree.
*/
void BinaryTree::Delete(KEY word)
{
	// if the tree is empty, don't do anything
	if(IsEmpty())
		return;

	// otherwise, call RemoveLeafNode which recursively find the
	// right LeafNode to remove and remove it from the tree.
	RemoveLeafNode(root, word);
}

/*
	bool BinaryTree::IsEmpty(void)

	Return true is the tree is empty.
*/
bool BinaryTree::IsEmpty(void)
{
	return (root == NULL);
}

/*
	void BinaryTree::RemoveLeafNode(LeafNode *pLeafNode, KEY word)

	Remove the item with the matching key.
	used in Delete function.
*/
void BinaryTree::RemoveLeafNode(LeafNode *pLeafNode, KEY word)
{
	// find the LeafNode with key word
	LeafNode *temp = FindHelper(root, word);

	// if found
	if(temp != NULL)
		RemoveLeafNodeHelper(temp);	// pass by reference

/*	// if not found, do nothing.
	if(pLeafNode == NULL)
		return;

	// if the item to delete is found, call helper function to delete this node
	if(strcmp(pLeafNode->key, word))
		RemoveLeafNodeHelper(pLeafNode);

	// if the word is smaller than the LeafNode key, search the left subtree
	else if(smaller(word, pLeafNode->key))
		RemoveLeafNode(pLeafNode, word);

	// otherwise, search the right subtree
	else
		RemoveLeafNode(pLeafNode, word);
*/

}

/*
	void BinaryTree::RemoveLeafNodeHelper(LeafNode *&rpLeafNode)

	Helper function for RemoveLeafNode to delete a specific node.
*/
void BinaryTree::RemoveLeafNodeHelper(LeafNode *&rpLeafNode)
{
	// if the LeafNode has no children
	if((rpLeafNode->GetLeft() == NULL) && (rpLeafNode->GetRight() == NULL)) {
		delete rpLeafNode;
		rpLeafNode = NULL;
		size--;
	}

	// if the LeafNode has only left child
	else if(rpLeafNode->GetRight() == NULL) {
		LeafNode *temp = rpLeafNode;
		rpLeafNode = rpLeafNode->GetLeft();
		// have to set the left pointer to NULL here, otherwise,
		// the left child will be deleted too.
		temp->SetLeft(NULL);
		delete temp;
		size--;
	}
 

	// if the LeafNode has only right child
	else if(rpLeafNode->GetLeft() == NULL) {
		LeafNode *temp = rpLeafNode;
		rpLeafNode = rpLeafNode->GetRight();
		// have to set the right pointer to NULL here, because 
		// the destructor only destruct the node with no children.
		temp->SetRight(NULL);
		delete temp;
		size--;
	}

	// if the LeafNode has left and right children
	else {
		LeafNode *temp = rpLeafNode;
		LeafNode *leftmost = FindLeftMostLeafNode(rpLeafNode->GetRight());
		leftmost->SetLeft(rpLeafNode->GetLeft());
		rpLeafNode = rpLeafNode->GetRight();

		temp->SetLeft(NULL);
		temp->SetRight(NULL);

		delete temp;
		size--;
	}

}

/*
	void BinaryTree::FindLeftMostLeafNode(LeafNode *pLeafNode)

	Return the left most LeafNode of the LeafNode past in.
*/
LeafNode *BinaryTree::FindLeftMostLeafNode(LeafNode *pLeafNode)
{
	if(pLeafNode->GetLeft() == NULL)
		return pLeafNode;
	else
		return FindLeftMostLeafNode(pLeafNode->GetLeft());
}

/*
	LeafNode *BinaryTree::Find(KEY word)

	Locate a LeafNode in the tree. Return a pointer to that LeafNode.
	if not found, return NULL.
	call FindHelper.
*/
LeafNode *BinaryTree::Find(KEY word)
{
	return FindHelper(root, word);
}

/*
	LeafNode *BinaryTree::FindHelper(LeafNode pLeafNode, KEY word)

	Helper function for Find.
*/
LeafNode *BinaryTree::FindHelper(LeafNode *pLeafNode, KEY word)
{
	// if not found, return NULL.
	if(pLeafNode == NULL)
		return NULL;

	// if the LeafNode of matching key is found, return its pointer.
	if(strcmp(pLeafNode->GetKey(), word) == 0)
		return pLeafNode;

	// if the word is smaller than the LeafNode key, search the left subtree
	else if(smaller(word, pLeafNode->GetKey()))
		return FindHelper(pLeafNode->GetLeft(), word);

	// otherwise, search the right subtree
	else
		return FindHelper(pLeafNode->GetRight(), word);
}

/*
	LeafNode &BinaryTree::First()

	Locate the smallest item in the tree.
*/
LeafNode *BinaryTree::First()
{
	return FindLeftMostLeafNode(root);
}

//	/*
//		LeafNode &BinaryTree::Next()

//		Traverse the tree usning in-order traversal.
//	*/
//	LeafNode &BinaryTree::Next();

/*
	void BinaryTree::Print() const

	Print the internal data in the BinaryTree.
*/
void BinaryTree::Print() const
{
	if(root == NULL)
		cout << "The tree is empty." << endl;
	else
		PrintHelper(root);
}

/*
	void BinaryTree::PrintHelper(LeafNode *pLeafNode) const

	Helper function for tree.
*/
void BinaryTree::PrintHelper(LeafNode *pLeafNode) const
{
	if(pLeafNode == NULL)
		return;

	if(pLeafNode->GetLeft() != NULL)
		PrintHelper(pLeafNode->GetLeft());
	

	pLeafNode->Print();

	if(pLeafNode->GetRight() != NULL) 
		PrintHelper(pLeafNode->GetRight());
}

/*
	int BinaryTree::GetSize() const

	Get the size of the tree (number of LeafNodes in the tree).
*/
int BinaryTree::GetSize() const
{
	return size;
}

Back	Top