Design an EmployeeInfo class that holds the following employee information: Employee ID Number: an integer

Employee Name: a string - Use template BinaryTree class to implement a binary tree whose nodes hold an instance of the EmployeeInfo class, the nodes should be sorted on the Employee ID number. - You should define constructors, and overload following operators

1. input and output operators (>>, <<)

2. comparison operators (>, <, ==), by comparing employee ID number.

Your driver program should build an EmployeeInfo tree, and display it in order

-----------------------------------------------------------------------------------

Output Example:

Enter employee ID: 4218

Enter employee name: Josh Plemmons

Enter employee ID: 1899

Enter employee name: Ashley Smith

Enter employee ID: 1275

Enter employee name: George McMullen

Enter employee ID: 1021

Enter employee name: John Williams

Enter employee ID: 2487

Enter employee name: Jennifer Twain

Enter employee ID: 0

Enter employee name: none

Employees are:

1021 John Williams

1275 George McMullen

1899 Ashley Smith

2487 Jennifer Twain

4218 Josh Plemmons Press any key to continue . . .

-----------------------------------------------------------

BinaryTree.h

#ifndef BINARYTREE_H

#define BINARYTREE_H

#include

using namespace std;

// Stack template

template

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;

public:

// Constructor

BinaryTree()

{ root = nullptr; }

// Destructor

~BinaryTree()

{ destroySubTree(root); }

// Binary tree operations

void insertNode(T);

bool searchNode(T);

void remove(T);

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

void BinaryTree::insert(TreeNode *&nodePtr, TreeNode *&newNode)

{

if (nodePtr == nullptr)

nodePtr = newNode; // Insert the node.

else if (newNode->value < nodePtr->value)

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

void BinaryTree::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

void BinaryTree::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

bool BinaryTree::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;

}

//**********************************************

// remove calls deleteNode to delete the *

// node whose value member is the same as num. *

//**********************************************

template

void BinaryTree::remove(T item)

{

deleteNode(item, root);

}

//********************************************

// deleteNode deletes the node whose value *

// member is the same as num. *

//********************************************

template

void BinaryTree::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

void BinaryTree::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. ";

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 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

void BinaryTree::displayInOrder(TreeNode *nodePtr) const

{

if (nodePtr)

{

displayInOrder(nodePtr->left);

cout << nodePtr->value << endl;

displayInOrder(nodePtr->right);

}

}

//****************************************************************

// The displayPreOrder member function displays the values *

// in the subtree pointed to by nodePtr, via preorder traversal. *

//****************************************************************

template

void BinaryTree::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

void BinaryTree::displayPostOrder(TreeNode *nodePtr) const

{

if (nodePtr)

{

displayPostOrder(nodePtr->left);

displayPostOrder(nodePtr->right);

cout << nodePtr->value << endl;

}

}

#endif