BinaryTree & EmployeeInfo; Comparative Overloading

[DiggyCode]

BinaryTree.h:

#pragma once
#include <iostream>
using namespace std;

// BinaryTree template
template <class T>
class BinaryTree {
private:
	struct TreeNode {
		T value; // The value in the node
		TreeNode *left; // Pointer to left child node
		TreeNode *right; // Pointer to right child node
	};

	TreeNode *root; // Pointer to the root node

	// Private member functions
	void insert(TreeNode *&, TreeNode *&);
	void destroySubTree(TreeNode *);
	void deleteNode(T, TreeNode *&);
	void makeDeletion(TreeNode *&);
	void displayInOrder(TreeNode *) const;
	void displayPreOrder(TreeNode *) const;
	void displayPostOrder(TreeNode *) const;
	void retrieveNode(TreeNode *);

	bool found; // An attempt to handle search function's found empID

public:
	// Constructor
	BinaryTree() {
		root = nullptr;
	}

	// Destructor
	~BinaryTree() {
		destroySubTree(root);
	}

	// Binary tree operations
	void insertNode(T);
	bool searchNode(T);
	void remove(T);

	// Function to return found values
	void retrieveNode() {
		retrieveNode(root);
	}

	void displayInOrder() const {
		displayInOrder(root);
	}

	void displayPreOrder() const {
		displayPreOrder(root);
	}

	void displayPostOrder() const {
		displayPostOrder(root);
	}
};

//*************************************************************
// insert accepts a TreeNode pointer and a pointer to a node. *
// The function inserts the node into the tree pointed to by  *
// the TreeNode pointer. This function is called recursively. *
//*************************************************************
template <class T>
void BinaryTree<T>::insert(TreeNode *&nodePtr, TreeNode *&newNode) {
	if (nodePtr == nullptr) {
		nodePtr = newNode; // Insert the node
	}
	else if (newNode->value.getEmpID() < nodePtr->value.getEmpID()) {
		insert(nodePtr->left, newNode); // Search the left branch
	}
	else {
		insert(nodePtr->right, newNode); // Search the right branch
	}
}

//***********************************************************
// insertNode creates a new node to hold num as its value,  *
// and passes it to the insert function.                    *
//***********************************************************
template <class T>
void BinaryTree<T>::insertNode(T item) {
	TreeNode *newNode = nullptr; // Pointer to a new node

	// Create a new node and store num in it.
	newNode = new TreeNode;
	newNode->value = item;
	newNode->left = newNode->right = nullptr;

	// Insert the node.
	insert(root, newNode);
}

//***************************************************
// destroySubTree is called by the destructor. It   *
// deletes all nodes in the tree.                   *
//***************************************************
template <class T>
void BinaryTree<T>::destroySubTree(TreeNode *nodePtr) {
	if (nodePtr) {
		if (nodePtr->left) {
			destroySubTree(nodePtr->left);
		}
		if (nodePtr->right) {
			destroySubTree(nodePtr->right);
		}
		delete nodePtr;
	}
}

//***************************************************
// searchNode determines if a value is present in   *
// the tree. If so, the function returns true.      *
// Otherwise, it returns false.                     *
//***************************************************
template <class T>
bool BinaryTree<T>::searchNode(T item) {
	TreeNode *nodePtr = root;

	while (nodePtr) {
		if (nodePtr->value.getEmpID() == item) {
			found = true;
			return found;
		}
		else if (item < nodePtr->value.getEmpID()) {
			nodePtr = nodePtr->left;
		}
		else {
			nodePtr = nodePtr->right;
		}
	}
	found = false;
	return found;
}

// 
template <class T>
void BinaryTree<T>::retrieveNode(TreeNode *nodePtr) {
	cout << nodePtr->value.getEmpID() << " " << nodePtr->value.getEmpName() << endl;
}

//***********************************************
// remove calls deleteNode to delete the        *
// node whose value member is the same as num.  *
//***********************************************
template <class T>
void BinaryTree<T>::remove(T item) {
	deleteNode(item, root);
}

//********************************************
// deleteNode deletes the node whose value   *
// member is the same as num.                *
//********************************************
template <class T>
void BinaryTree<T>::deleteNode(T item, TreeNode *&nodePtr) {
	if (item < nodePtr->value) {
		deleteNode(item, nodePtr->left);
	}
	else if (item > nodePtr->value) {
		deleteNode(item, nodePtr->right);
	}
	else {
		makeDeletion(nodePtr);
	}
}

//***********************************************************
// makeDeletion takes a reference to a pointer to the node  *
// that is to be deleted. The node is removed and the       *
// branches of the tree below the node are reattached.      *
//***********************************************************
template <class T>
void BinaryTree<T>::makeDeletion(TreeNode *&nodePtr) {
	// Define a temporary pointer to use in reattaching
	// the left subtree.
	TreeNode *tempNodePtr = nullptr;

	if (nodePtr == nullptr) {
		cout << "Cannot delete empty node.\n";
	}
	else if (nodePtr->right == nullptr) {
		tempNodePtr = nodePtr;
		nodePtr = nodePtr->left; // Reattach the left child
		delete tempNodePtr;
	}
	else if (nodePtr->left == nullptr) {
		tempNodePtr = nodePtr;
		nodePtr = nodePtr->right; // Reattach the right child
		delete tempNodePtr;
	}
	// If the node has two children.
	else {
		// Move one node to the right.
		tempNodePtr = nodePtr->right;

		// Go to the end left node.
		while (tempNodePtr->left) {
			tempNodePtr = tempNodePtr->left;
		}

		// Reattach the left subtree.
		tempNodePtr->left = nodePtr->left;
		tempNodePtr = nodePtr;

		// Reattach the right subtree.
		nodePtr = nodePtr->right;
		delete tempNodePtr;
	}
}

//**************************************************************
// The displayInOrder member function displays the values      *
// in the subtree pointed to by nodePtr, via inorder traversal.*
//**************************************************************
template <class T>
void BinaryTree<T>::displayInOrder(TreeNode *nodePtr) const {
	if (nodePtr) {
		displayInOrder(nodePtr->left);
		cout << nodePtr->value.getEmpID() << " " << nodePtr->value.getEmpName() << endl;
		displayInOrder(nodePtr->right);
	}
}

//***************************************************************
// The displayPreOrder member function displays the values	    *
// in the subtree pointed to by nodePtr, via preorder traversal.*
//***************************************************************
template <class T>
void BinaryTree<T>::displayPreOrder(TreeNode *nodePtr) const {
	if (nodePtr) {
		cout << nodePtr->value << endl;
		displayPreOrder(nodePtr->left);
		displayPreOrder(nodePtr->right);
	}
}

//****************************************************************
// The displayPostOrder member function displays the values      *
// in the subtree pointed to by nodePtr, via postorder traversal.*
//****************************************************************
template <class T>
void BinaryTree<T>::displayPostOrder(TreeNode *nodePtr) const {
	if (nodePtr) {
		displayPostOrder(nodePtr->left);
		displayPostOrder(nodePtr->right);
		cout << nodePtr->value << endl;
	}
}
}

[DiggyCode]

Apologies everyone for that ghastly amount of code.

I'm having an issue regarding my use of comparative operators. I've looked up the previous topics that some have asked here before regarding this issue, but most are incomplete topics that never got a true resolved ending. I'm hoping to have assistance from beginning to end on what is supposed to be simple, yet troublesome when I'm trying to apply it.

So far, I have these two persistent errors:

binarytree.h(125): error C2678: binary '==': no operator found which takes a left-hand operand of type 'int' (or there is no acceptable conversion)

binarytree.h(129): error C2678: binary '<': no operator found which takes a left-hand operand of type 'EmployeeInfo' (or there is no acceptable conversion)

What's bothering me is the difference of left-hand and right-hand operands. I'm not the type to really use the actual technical terms, which I guess is my crutch when these kinds of errors pop up. What I'm trying to get from this is that there is meant to be a '==' and '<' overload in EmployeeInfo, right?

Well, here's the EmployeeInfo.h:

#pragma once
#include <string>
using namespace std;

class EmployeeInfo {
	private:
		int empID;
		string empName;

	public:
		// Default & Overload Constructor
		EmployeeInfo();

		// Mutators
		void setEmpID(int);
		void setEmpName(string);

		// Accessors
		int getEmpID();
		string getEmpName();

		// Operator < Overload
		//bool operator < (const EmployeeInfo &);
		bool operator < (const EmployeeInfo &y) {
			if (empID < y.empID) {
				return true;
			}
			return false;
		}

		// Operator == Overload
		//bool operator == (const EmployeeInfo &);
		bool operator == (const EmployeeInfo &z) {
			if (empID == z.empID) {
				return true;
			}
			else {
				return false;
			}
		}
};

No matter where I place these overloads in EmployeeInfo.h or .cpp, these overload errors stick around. If I place these overloads in BinaryTree.h, a whole new set of problems occur first since it doesn't know what 'EmployeeInfo' is, of course.

So, do these overloads need to be mentioned in BinaryTree? Or are they meant to be in EmployeeInfo? If the latter, how are they meant to be there, exactly?

I can provide the other files if they are needed. The purpose is to create a program/application that can handle an employee's ID and Name in a BinaryTree. The user is only meant to search for an employee based on their ID, a search will be called, and will come back outputting a matching employee's ID and Name.

[tpb]

The problem is that you are trying to compare an integer with an EmployeeInfo object. You need to compare an EmployeeInfo object with another EmployeeInfo object to use your overloads. Instead, you are explicitly accessing the employee ID integer in your binary tree code, but the generic binary tree shouldn't know the details of the type that it holds. It should be more like the following. The "found" variable in the binary tree code isn't needed so I removed it; you should remove it from the top of the code, too.

template <class T>
bool BinaryTree<T>::searchNode(T item) {
	TreeNode *nodePtr = root;

	while (nodePtr) {
		if (nodePtr->value == item) {
			return true;
		}
		else if (item < nodePtr->value) {
			nodePtr = nodePtr->left;
		}
		else {
			nodePtr = nodePtr->right;
		}
	}
	return false;
}

[DiggyCode]

So, because I thought I needed to specify what value I wanted to be found, I only made it worse! This is what happens when I get desperate and look up other people's attempt at the same assignment, but they too were having issues. Some showed it worked but, looks like I only fooled myself thinking they were making it work.

Thanks again tpb. I see another issue that I was trying to see whether or not it worked. Since I am just understanding how to use Binary Trees, it of course didn't work.

Like I mentioned originally, I am trying to retrieve an Employee's ID and Name based on a user's input of an ID.

Here's my attempt in main:

#include <iostream>
#include "BinaryTree.h"
#include "EmployeeInfo.h"
using namespace std;

int main() {

	// Declaring user int and EmployeeInfo
	int userSearchID;
	EmployeeInfo user;

	// Creating EmployeeInfo Objects
	EmployeeInfo emp1;
	emp1.setEmpID(1021);
	emp1.setEmpName("John Williams");
	EmployeeInfo emp2;
	emp2.setEmpID(1057);
	emp2.setEmpName("Bill Witherspoon");
	EmployeeInfo emp3;
	emp3.setEmpID(2487);
	emp3.setEmpName("Jennifer Twain");
	EmployeeInfo emp4;
	emp4.setEmpID(3769);
	emp4.setEmpName("Sophia Lancaster");
	EmployeeInfo emp5;
	emp5.setEmpID(1017);
	emp5.setEmpName("Debbie Reece");
	EmployeeInfo emp6;
	emp6.setEmpID(1275);
	emp6.setEmpName("George McMullen");
	EmployeeInfo emp7;
	emp7.setEmpID(1899);
	emp7.setEmpName("Ashley Smith");
	EmployeeInfo emp8;
	emp8.setEmpID(4218);
	emp8.setEmpName("Josh Plemmons");

	// Creating a binary tree
	BinaryTree<EmployeeInfo> tree;

	// Inserting int values
	tree.insertNode(emp1);
	tree.insertNode(emp2);
	tree.insertNode(emp3);
	tree.insertNode(emp4);
	tree.insertNode(emp5);
	tree.insertNode(emp6);
	tree.insertNode(emp7);
	tree.insertNode(emp8);

	// Display InOrder
	tree.displayInOrder();
	cout << endl;

	cout << "Enter the employee's ID: ";
	cin >> userSearchID;
	user.setEmpID(userSearchID);
	cout << endl;

	cout << "Searching for employee with ID #" << userSearchID << "...\n";

	if (tree.searchNode(user)) {
		cout << "Employee found. Displaying info...\n";
		tree.retrieveNode();
	}
	else {
		cout << "Employee not found. Try again.\n";
	}

	cout << endl;
	return 0;
}

I had a feeling that my attempt wouldn't work, but I'm not getting a good idea on how to turn a boolean search result into an actual return of values. BTW, retrieveNode is my custom function. It is not part of the original BinaryTree.h file.

[tpb]

There is no way to turn a boolean return value into the information from the record that was found. It's best to return a pointer to the found record or a nullptr if it wasn't found. Are you allowed to return a T* from searchNode?

template <class T>
T* BinaryTree<T>::searchNode(T item) {
	TreeNode *nodePtr = root;

	while (nodePtr) {
		if (nodePtr->value == item) {
			return &nodePtr->value;
		}
		else if (item < nodePtr->value) {
			nodePtr = nodePtr->left;
		}
		else {
			nodePtr = nodePtr->right;
		}
	}
	return nullptr;
}

// in main

	EmployeeInfo *emp = tree.searchNode(user);
	if (emp != nullptr) {
		cout << "Employee found. Displaying info...\n";
		cout << emp->getEmpName() << '\n';
	}
	else {
		cout << "Employee not found. Try again.\n";
	}

[DiggyCode]

I was not instructed to never touch BinaryTree, just instructed to search for an employee's information and have a way to output the found information.

In case I am not meant to touch the boolean searchNode, is there another way that will still allow me to output a found info?

[tpb]

It's kind of silly, and also wasteful since you search the tree twice, but you could do something like this:

// Add a new member function "findNode" to BinaryTree

template <class T>
T* BinaryTree<T>::findNode(T item) {
	TreeNode *nodePtr = root;

	while (nodePtr) {
		if (nodePtr->value == item) {
			return &nodePtr->value;
		}
		else if (item < nodePtr->value) {
			nodePtr = nodePtr->left;
		}
		else {
			nodePtr = nodePtr->right;
		}
	}
	return nullptr;
}

// Either copy it's implementation for searchNode (but return true and false instead of pointers)
// or just have searchNode use it like this:

template <class T>
bool BinaryTree<T>::searchNode(T item) {
	return findNode(item) != nullptr;
}

// then in main
	if (tree.searchNode(user)) {
		EmployeeInfo *emp = tree.findNode(user);
		cout << "Employee found. Displaying info...\n";
		cout << emp->getEmpName() << '\n';
	}
	else {
		cout << "Employee not found. Try again.\n";
	}

[DiggyCode]

Thank you, tpb.
For now, I'll keep the altered T* searchNode() and see what comes from that. You've helped me twice and showed me how I'm not paying enough attention to what's actually going on, haha. I guess it's expected since I really am learning c++ under this year alone! In three separate sets of 8 weeks, to boot.

Anyway, excuses aside, I am glad you're willing to assist whenever you have the time. I have no further issues with this.