Binary Search Tree with a Class?

[michee65]

I am trying to implement a Binary Search Tree from a template. I am trying to have the list sort an Employee object. The Employee class has two member variables, an ID number (int) and a name (string). I want the list to sort them in order by the ID number. I have the Binary Search Tree template, Binary Tree template, and Binary Node template. The Binary Search tree works with int and string, but not with my Employee Object. Any input will be greatly appreciated!

Binary Search Tree Class:

// Binary Search Tree ADT
// Created by Frank M. Carrano and Tim Henry.
// Modified by:

#ifndef _BINARY_SEARCH_TREE
#define _BINARY_SEARCH_TREE

#include "BinaryTree.hpp"
#include "Employee.hpp"


template<class ItemType>
class BinarySearchTree : public BinaryTree<ItemType>
{
private:
// internal insert node: insert newNode in nodePtr subtree
BinaryNode<ItemType>* _insert(BinaryNode<ItemType>* nodePtr, BinaryNode<ItemType>* newNode);

// internal remove node: locate and delete target node under nodePtr subtree
BinaryNode<ItemType>* _remove(BinaryNode<ItemType>* nodePtr, const ItemType target, bool & success);

// delete target node from tree, called by internal remove node
BinaryNode<ItemType>* deleteNode(BinaryNode<ItemType>* targetNodePtr);

// remove the leftmost node in the left subtree of nodePtr
BinaryNode<ItemType>* removeLeftmostNode(BinaryNode<ItemType>* nodePtr, ItemType & successor);

// search for target node
BinaryNode<ItemType>* findNode(BinaryNode<ItemType>* treePtr, const ItemType & target) const;

//breadth first traversal // called by breadthTraverse
//void _breadthTraverse(void visit(ItemType &), BinaryNode<ItemType>* nodePtr) const;




public:
// insert a node at the correct location
bool insert(const ItemType & newEntry);
// remove a node if found
bool remove(const ItemType & anEntry);
// find a target node
bool getEntry(const ItemType & target, ItemType & returnedItem) const;






};
///////////////////////// public function definitions ///////////////////////////

template<class ItemType>
bool BinarySearchTree<ItemType>::insert(const ItemType & newEntry)
{
BinaryNode<ItemType>* newNodePtr = new BinaryNode<ItemType>(newEntry);
this->rootPtr = _insert(this->rootPtr, newNodePtr);
return true;
}

template<class ItemType>
bool BinarySearchTree<ItemType>::remove(const ItemType & target)
{
bool isSuccessful = false;
this->rootPtr = _remove(this->rootPtr, target, isSuccessful);
return isSuccessful;
}

template<class ItemType>
bool BinarySearchTree<ItemType>::getEntry(const ItemType& anEntry, ItemType & returnedItem) const
{
bool success = false;
if(findNode(this->rootPtr,anEntry))
{
success = true;
}
return success;

}



//////////////////////////// private functions ////////////////////////////////////////////

template<class ItemType>
BinaryNode<ItemType>* BinarySearchTree<ItemType>::_insert(BinaryNode<ItemType>* nodePtr,
BinaryNode<ItemType>* newNodePtr)
{
if(nodePtr == nullptr)
{
return newNodePtr;

}
else if(nodePtr->getItem() > newNodePtr->getItem())
{
nodePtr->setLeftPtr(_insert(nodePtr->getLeftPtr(), newNodePtr));
}
else
{
nodePtr->setRightPtr(_insert(nodePtr->getRightPtr(), newNodePtr));
}
return nodePtr;
//return 0; // <=== remove this when done
}

template<class ItemType>
BinaryNode<ItemType>* BinarySearchTree<ItemType>::_remove(BinaryNode<ItemType>* nodePtr,
ItemType target,
bool & success)

{
if (nodePtr == 0)
{
success = false;
return 0;
}
if (nodePtr->getItem() > target)
nodePtr->setLeftPtr(_remove(nodePtr->getLeftPtr(), target, success));
else if (nodePtr->getItem() < target)
nodePtr->setRightPtr(_remove(nodePtr->getRightPtr(), target, success));
else
{
nodePtr = deleteNode(nodePtr);
success = true;
}
return nodePtr;
}

template<class ItemType>
BinaryNode<ItemType>* BinarySearchTree<ItemType>::deleteNode(BinaryNode<ItemType>* nodePtr)
{
if (nodePtr->isLeaf())
{
delete nodePtr;
nodePtr = 0;
return nodePtr;
}
else if (nodePtr->getLeftPtr() == 0)
{
BinaryNode<ItemType>* nodeToConnectPtr = nodePtr->getRightPtr();
delete nodePtr;
nodePtr = 0;
return nodeToConnectPtr;
}
else if (nodePtr->getRightPtr() == 0)
{
BinaryNode<ItemType>* nodeToConnectPtr = nodePtr->getLeftPtr();
delete nodePtr;
nodePtr = 0;
return nodeToConnectPtr;
}
else
{
ItemType newNodeValue;
nodePtr->setRightPtr(removeLeftmostNode(nodePtr->getRightPtr(), newNodeValue));
nodePtr->setItem(newNodeValue);
return nodePtr;
}
}

template<class ItemType>
BinaryNode<ItemType>* BinarySearchTree<ItemType>::removeLeftmostNode(BinaryNode<ItemType>* nodePtr,
ItemType & successor)
{
if (nodePtr->getLeftPtr() == 0)
{
successor = nodePtr->getItem();
return deleteNode(nodePtr);
}
else
{
nodePtr->setLeftPtr(removeLeftmostNode(nodePtr->getLeftPtr(), successor));
return nodePtr;
}
}


template<class ItemType>
BinaryNode<ItemType>* BinarySearchTree<ItemType>::findNode(BinaryNode<ItemType>* nodePtr,
const ItemType & target) const
{
if(nodePtr == nullptr)
{
return nullptr;
}
else if(nodePtr->getItem() == target)
{
return nodePtr;
}
else if(nodePtr->getItem() > target)
{
return findNode(nodePtr->getLeftPtr(), target);
}
else
{
return findNode(nodePtr->getRightPtr(),target);
}



}


#endif

[jonnin]

Did you remember to overload the big 3 & the comparison operators for your data class? The tree can't use it if it can't do comparisons and copies etc.

nodePtr->getItem() == target

nodePtr->getItem() > target

etc.

[michee65]

Thanks! So I should overload the operators in my Employee class right?

[jonnin]

right, you need to be able to do to employee the same comparisons and assignments that work by default for basic types like integers.
The big 3 thing prevents other bugs and issues that you may not encounter here if you ONLY overload the ones you need. It is usually best to go ahead and add them even if you don't use them, if you have one of the 3.

You should also go ahead and define a full set. For example you CAN just overload > and not < but it is weird to only have 1/2 the set.

I would make sure your class supports these:

assignment operator (=)
equality (==)
LT (<)
GT(>)
LTE(<=)
GTE(>=)
NE (!=)

and check to see (I didnt look closely) if you need a copy -constructor (this triggers the big 3).