In this program you are going to use the binary tree class you created in Assign

Question

In this program you are going to use the binary tree class you created in Assignment 1 this week. First create a class called EmployeeInfo that holds two private data members. One data member is an integer called empID which holds the id number of the employee. The second data member is a string called empName which holds the full name of the employee. The program will create an instance of the binary tree class with a data type of EmployeeInfo (BinaryTree<EmployeeInfo>). The binary tree will be sorted by the Employee ID number found in the EmployeeInfo class. The program should then allow the user to search for Employee by the Employee ID. If the employee is found in the tree, its name and ID should be displayed. If not, a message should be displayed indicating that it was not found. Sample data would be

1021       John Williams

1057       Bill Witherspoon

2487       Jennifer Twain

3769       Sophia Lancaster

1017       Debbie Reece

1275       George McMullen

1899       Ashley Smith

4218       Josh Plemmons

Explanation / Answer

#ifndef BINARYTREE_H #define BINARYTREE_H #include using namespace std; // This class is a template class that creates a binary // tree that can hold values of any data type. It has // functions to insert a node, delete a node, display the // tree In Order, Pre Order and Post Order, search for a // value, count the number of total nodes, left nodes, // and a function to determine the height of the tree. 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; int counter(TreeNode *); int leafCounter(TreeNode *); int height(TreeNode *); public: // Constructor BinaryTree() { root = NULL; } // Destructor ~BinaryTree() { destroySubTree(root); } // Binary tree operations void insertNode(T); bool searchNode(T); void remove(T); void displayPreOrder() const { displayPreOrder(root); } void displayInOrder() const { displayInOrder(root); } void displayPostOrder() const { displayPostOrder(root); } // Node counter int counter() { int n = counter(root); return n; } // Leaf counter int leafCounter() { int leaf = leafCounter(root); return leaf; } // Height of the tree int height() { int h = height(root); return h; } }; //********************************************************* // insert function accepts a TreeNode pointer and a * // pointer to a node. The function inserts the node into * // the tree pointer to by the TreeNode pointer. This * // function is call recursively. * //********************************************************* template void BinaryTree::insert(TreeNode *&nodePtr, TreeNode *&newNode) { if (nodePtr == NULL) nodePtr = newNode; // Insert the node else if (newNode->value value) insert(nodePtr->left, newNode); // Search the left branch else insert(nodePtr->right, newNode);// Search the right branch } //********************************************************* // insertNode creates anew node to hold num as its value * // and passes it to the insert function. * //********************************************************* template void BinaryTree::insertNode(T item) { TreeNode *newNode; // Pointer to a new node // Create anew node and store num in it newNode = new TreeNode; newNode->value = item; newNode->left = newNode->right = NULL; // 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 value) nodePtr = nodePtr->left; else nodePtr = nodePtr->right; } return false; } //********************************************************* // remove calls deleteNode to delete the node whode 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 value) deleteNode(item, nodePtr->left); else if (item > nodePtr->value) deleteNode(item, nodePtr->right); else makeDeletion(nodePtr); } //********************************************************* // makeDeletion takes a reference to apointer 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; if (nodePtr == NULL) cout right == NULL) { tempNodePtr = nodePtr; nodePtr = nodePtr->left; // Reattach the left child delete tempNodePtr; } else if (nodePtr->left == NULL) { tempNodePtr = nodePtr; nodePtr = nodePtr->right; // Reattach the right child delete tempNodePtr; } } //********************************************************* // The displayInOrder 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 left) right)) return (height(nodePtr->right) +1); else return (height(nodePtr->left) +1); } #endif

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.