C++ visual studio program. Please create the entire program with the necessary o
ID: 3770854 • Letter: C
Question
C++ visual studio program. Please create the entire program with the necessary output please.
Create a class (BinaryTree) template that will create a binary tree that can hold values of any data type. The class should provide functions to insert a node, a function to delete a node, functions to display the tree In Order, Pre Order and Post Order. It should also provide a member function to search the tree for a value. The class should provide a function that counts the number of nodes in the tree, a function to count the number leaf nodes in the tree, and a function that determines the height of the tree. The height of a tree is the number of levels the tree has. Write a program that shows all these functions work.
Explanation / Answer
#ifndef BINARYTREE_H
#define BINARYTREE_H
#include <iostream>
using namespace std;
template <class T>
class BinaryTree
{
private:
struct TreeNode
{
T value;
TreeNode *left;
TreeNode *right;
};
TreeNode *root;
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:
BinaryTree()
{
root = NULL;
}
~BinaryTree()
{
destroySubTree(root);
}
void insertNode(T);
bool searchNode(int);
void remove(T);
void displayPreOrder() const
{
displayPreOrder(root);
}
void displayInOrder() const
{
displayInOrder(root);
}
void displayPostOrder() const
{
displayPostOrder(root);
}
};
template <class T>
void BinaryTree<T>::insert(TreeNode *&nodePtr, TreeNode *&newNode)
{
if (nodePtr == NULL)
nodePtr = newNode;
else if (newNode->value < nodePtr->value)
insert(nodePtr->left, newNode);
else
insert(nodePtr->right, newNode);
}
template <class T>
void BinaryTree<T>::insertNode(T item)
{
TreeNode *newNode;
newNode = new TreeNode;
newNode->value = item;
newNode->left = newNode->right = NULL;
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)
{
TreeNode *tempNodePtr;
if (nodePtr == NULL)
cout << "Cannot delete empty node. ";
else if (nodePtr->right == NULL)
{
tempNodePtr = nodePtr;
nodePtr = nodePtr->left;
delete tempNodePtr;
}
else if (nodePtr->left == NULL)
{
tempNodePtr = nodePtr;
nodePtr = nodePtr->right;
delete tempNodePtr;
}
}
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);
}
}
template <class T>
void BinaryTree<T>::displayPreOrder(TreeNode *nodePtr) const
{
if (nodePtr)
{
cout << nodePtr->value.getEmpID() << " "
<< nodePtr->value.getEmpName() << 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.getEmpID() << " "
<< nodePtr->value.getEmpName() << endl;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.