C++:

I need help with writing the code for 3 methods.

1). void setEntry(const KeyType& aKey, const ItemType& item) const throw(NotFoundException, InvalidSetEntryRequest);

and

2). BinarySearchTree& operator=(const BinarySearchTree& rightHandSide);

and

3). BinarySearchTree(const BinarySearchTree& tree);

Here is my code:

BST.cpp

#include "BinarySearchTree.h"

//------------------------------------------------------------

// Protected Utility Methods Section:

// Recursive helper methods for the public methods.

//------------------------------------------------------------

template

BinaryNode* BinarySearchTree::insertInorder(BinaryNode* subTreePtr,

BinaryNode* newNode)

{

if (subTreePtr == NULL)

{

return newNode;

}

else

{

if (newNode->getItem() > subTreePtr->getItem())

{

BinaryNode* tempPtr = inorderInsertion(subTreePtr->getRightChildPtr(), newNode);

subTreePtr->setRightChildPtr(tempPtr);

}

else

{

BinaryNode* tempPtr = inorderInsertion(subTreePtr->getLeftChildPtr(), newNode);

subTreePtr->setLeftChildPtr(tempPtr);

}

return subTreePtr;

}

}

template

BinaryNode* BinarySearchTree::removeValue(BinaryNode* subTreePtr,

KeyType aKey, bool& success)

{

if (subTreePtr == NULL)

{

success = false;

return NULL;

}

else if (subTreePtr->getItem() == aKey)

{

subTreePtr = removeNode(subTreePtr);

success = true;

return subTreePtr;

}

else

{

if (subTreePtr->getItem() > aKey)

{

BinaryNode* tempPtr = removeValue(subTreePtr->getLeftChildPtr(), aKey, success);

subTreePtr->setLeftChildPtr(tempPtr);

}

else

{

BinaryNode* tempPtr = removeValue(subTreePtr->getRightChildPtr(), aKey, success);

subTreePtr->setRightChildPtr(tempPtr);

}

return subTreePtr;

}

}

template

BinaryNode* BinarySearchTree::removeNode(BinaryNode* nodePtr)

{

if (nodePtr->isLeaf() == true)

{

delete nodePtr;

nodePtr = NULL;

return (nodePtr);

}

//else if (nodePtr->getLeftChildPtr() == NULL)

//{

//BinaryNode* nodeToConnectPtr = nodePtr->getRightChildPtr();

//delete nodePtr;

//nodePtr = NULL;

//return nodeToConnectPtr;

//}

//else if (nodePtr->getRightChildPtr() == NULL)

//{

// BinaryNode* nodeToConnectPtr = nodePtr->getLeftChildPtr();

// delete nodePtr;

// nodePtr = NULL;

// return nodeToConnectPtr;

//}

//else

//{

// ItemType newNodeValue;

// nodePtr->setRightChildPtr(removeLeftmostNode(nodePtr->getRightChildPtr(), newNodeValue));

// nodePtr->setItem(newNodeValue);

// return nodePtr;

// }

else if ((nodePtr->getLeftChildPtr() == NULL && nodePtr->getRightChildPtr() != NULL) || (nodePtr->getRightChildPtr() == NULL && nodePtr->getLeftChildPtr() != NULL))

{

BinaryNode* nodeToConnectPtr;

if (nodePtr->getLeftChildPtr() != NULL)

{

nodeToConnectPtr = nodePtr->getLeftChildPtr();

}

else

{

nodeToConnectPtr = nodePtr->getRightChildPtr();

}

delete nodePtr;

nodePtr = NULL;

return nodeToConnectPtr;

}

else

{

ItemType newNodeValue;

BinaryNode* tempPtr = removeLeftmostNode(nodePtr->getRightChildPtr(), newNodeValue);

nodePtr->setRightChildPtr(tempPtr);

nodePtr->setItem(newNodeValue);

}

}

template

BinaryNode* BinarySearchTree::removeLeftmostNode(BinaryNode* subTreePtr,

ItemType& inorderSuccessor)

{

if (subTreePtr->getLeftChildPtr() == NULL)

{

inorderSuccessor = subTreePtr->getItem();

return removeNode(subTreePtr);

}

else

{

subTreePtr->setLeftChildPtr(removeLeftmostNode(subTreePtr->getLeftChildPtr(), inorderSuccessor));

return subTreePtr;

}

}

template

BinaryNode* BinarySearchTree::findNode(BinaryNode* treePtr,

KeyType aKey) const

{

if (treePtr == NULL)

{

return NULL;

}

else if (treePtr->getItem() == aKey)

{

return treePtr;

}

else if (treePtr->getItem() > aKey)

{

return findNode(treePtr->getLeftChildPtr(), aKey);

}

else

{

return findNode(treePtr->getRightChildPtr(), aKey);

}

}

template

void BinarySearchTree::preorder(void visit(ItemType&), BinaryNode* treePtr) const

{

if (treePtr != NULL)

{

ItemType theItem = treePtr->getItem();

visit(theItem);

preorder(visit, treePtr->getLeftChildPtr());

preorder(visit, treePtr->getRightChildPtr());

}

}

template

void BinarySearchTree::inorder(void visit(ItemType&), BinaryNode* treePtr) const

{

if (treePtr != NULL)

{

inorder(visit, treePtr->getLeftChildPtr());

ItemType theItem = treePtr->getItem();

visit(theItem);

inorder(visit, treePtr->getRightChildPtr());

}

}

template

void BinarySearchTree::postorder(void visit(ItemType&), BinaryNode* treePtr) const

{

if (treePtr != NULL)

{

postorder(visit, treePtr->getLeftChildPtr());

postorder(visit, treePtr->getRightChildPtr());

ItemType theItem = treePtr->getItem();

visit(theItem);

}

}

//------------------------------------------------------------

// Constructor and Destructor Section.

//------------------------------------------------------------

template

BinarySearchTree::BinarySearchTree()

{

rootPtr = NULL;

}

template

BinarySearchTree::BinarySearchTree(const ItemType& rootItem)

{

rootPtr = new BinaryNode(rootItem, NULL, NULL);

}

template

BinarySearchTree::BinarySearchTree(const BinarySearchTree& tree)

{

}

template

BinarySearchTree::~BinarySearchTree()

{

clear();

}

//------------------------------------------------------------

// Public Methods Section.

//------------------------------------------------------------

template

bool BinarySearchTree::isEmpty() const

{

return rootPtr == NULL;

}

template

int BinarySearchTree::getHeight() const

{

if (rootPtr == NULL)

{

return 0;

}

else

{

return 1 + max(getHeight(rootPtr->getLeftChildPtr()), getHeight(rootPtr->getRightChildPtr()));

}

}

template

int BinarySearchTree::getNumberOfNodes() const

{

if (rootPtr == NULL)

{

return 0;

}

else

{

return 1 + getNumberOfNodes(rootPtr->getLeftChildPtr()) + getNumberOfNodesHelper(rootPtr->getRightChildPtr());

}

}

template

bool BinarySearchTree::add(const ItemType& newEntry)

{

BinaryNode* newNodePtr = new BinaryNode(newEntry);

rootPtr = insertInorder(rootPtr, newNodePtr);

return true;

}

template

bool BinarySearchTree::remove(const KeyType& aKey)

{

bool isSuccessful = false;

rootPtr = removeValue(rootPtr, aKey, isSuccessful);

return isSuccessful;

}

template

ItemType BinarySearchTree::getEntry(const KeyType& aKey) const throw(NotFoundException)

{

BinaryNode* nodeWithEntry = findNode(rootPtr, aKey);

if (nodeWithEntry == NULL)

{

throw NotFoundException("Entry not found in tree.");

}

else

{

return nodeWithEntry->getItem();

}

}

template

void BinarySearchTree::setEntry(const KeyType& aKey, const ItemType& item) const throw(NotFoundException, InvalidSetEntryRequest)

{

if (add(item) == true)

{

BinaryNode* newNodePtr = new BinaryNode(newEntry);

rootPtr = inorderInsertion(rootPtr, newNodePtr);

}

else

{

throw NotFoundException("Can not add to tree."), InvalidSetEntryRequest("Invalud set Entry Request.")

}

}

template

bool BinarySearchTree::contains(const KeyType& aKey) const

{

if (findNode(rootPtr, aKey) != NULL)

{

return true;

}

else

{

return false;

}

}

template

void BinarySearchTree::clear()

{

if (rootPtr != NULL)

{

clear(rootPtr->leftChildPtr);

clear(rootPtr->rightChildPtr);

delete rootPtr;

if (rootPtr->leftChildPtr != NULL)

{

rootPtr->leftChildPtr = NULL;

}

if (rootPtr->rightChildPtr != NULL)

{

rootPtr->rightChildPtr = NULL;

}

rootPtr = NULL;

}

}

//------------------------------------------------------------

// Public Traversals Section.

//------------------------------------------------------------

template

void BinarySearchTree::preorderTraverse(void visit(ItemType&)) const

{

preorder(visit, rootPtr);

}

template

void BinarySearchTree::inorderTraverse(void visit(ItemType&)) const

{

inorder(visit, rootPtr);

}

template

void BinarySearchTree::postorderTraverse(void visit(ItemType&)) const

{

postorder(visit, rootPtr);

}

//------------------------------------------------------------

// Overloaded Operator Section.

//------------------------------------------------------------

template

BinarySearchTree& BinarySearchTree::operator=(const BinarySearchTree& rightHandSide)

{

}