C++ Write your own version of a class template that will create a binary tree th

Question

C++

Write your own version of a class template that will create a binary tree that can hold values of any data type. Include a member function in the template you designed that counts and returns the number of nodes in the tree. Design an EmployeeInfo class that holds the following employee information:

• Employee ID Number: an integer

• Employee Name: a string

Next, use the template you designed to implement a binary tree whose nodes hold an instance of the EmployeeInfo class. The nodes should be sorted on the Employee ID number. Test the binary tree by inserting nodes with the following information.

EmployeeID Number Name

1021 John Williams

1057 Bill Witherspoon

2487 Jennifer Twain

3769 Sophia Lancaster

1017 Debbie Reece

1275 George McMullen

1899 Ashley Smith

4218 Josh Plemmons

Your program should allow the user to enter an ID number, and then search the tree for the number. If the number is found, it should display the employee’s name. If the node is not found, it should display a message indicating so. Include a member function, for the template you designed that counts and returns the number of nodes in the tree. Your program must show a menu with at least the options to insert, search and count employees.

Explanation / Answer

#ifndef BINARYTREE_H
#define BINARYTREE_H
#include <iostream>
using namespace std;

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

template <class T>
void BinaryTree<T>::insert(TreeNode *&nodePtr, TreeNode *&newNode)
{
if (nodePtr == NULL)
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
}

template <class T>
void BinaryTree<T>::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);
}

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;
}
}
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;
}
template <class T>
void BinaryTree<T>::remove(T item)
{
deleteNode(item, root);
}

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);
}
template <class T>
void BinaryTree<T>::makeDeletion(TreeNode *&nodePtr)
{
// Define a temporary pointer to use in reattaching
// the left subtree
TreeNode *tempNodePtr;

if (nodePtr == NULL)
cout << "Cannot delete empty node. ";
else if (nodePtr->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;
}

}

template <class T>
void BinaryTree<T>::displayInOrder(TreeNode *nodePtr) const
{
if (nodePtr)
{
displayInOrder(nodePtr->left);
cout << nodePtr->value.getEmpID() << " "
<< getEmpName() << endl;
displayInOrder(nodePtr->right);
}
}

template <class T>
void BinaryTree<T>::displayPreOrder(TreeNode *nodePtr) const
{
if (nodePtr)
{
cout << nodePtr->value << endl;
displayInOrder(nodePtr->left);
displayInOrder(nodePtr->right);
}
}
template <class T>
void BinaryTree<T>::displayPostOrder(TreeNode *nodePtr) const
{
if (nodePtr)
{
displayInOrder(nodePtr->left);
displayInOrder(nodePtr->right);
cout << nodePtr->value << endl;
}
}

template <class T>
int BinaryTree<T>::counter(TreeNode *nodePtr)
{
if (nodePtr == NULL)
return 0;
else
return counter(nodePtr->left) +1+ counter(nodePtr->right);
}

template <class T>
int BinaryTree<T>::leafCounter(TreeNode *nodePtr)
{
if (nodePtr == NULL)
return 0;
else if (nodePtr->left == NULL && nodePtr->right == NULL)
return 1;
else
return leafCounter(nodePtr->left) + leafCounter(nodePtr->right);
}

template <class T>
int BinaryTree<T>::height(TreeNode *nodePtr)
{

if(nodePtr == NULL)
return -1;
if (height(nodePtr->left) <= height(nodePtr->right))
return (height(nodePtr->right) +1);
else
return (height(nodePtr->left) +1);

}
#endif

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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