Help C++ Implement a couple operations for the binary search tree code from Alla
ID: 3728103 • Letter: H
Question
Help C++
Implement a couple operations for the binary search tree code from Allard (https://github.com/Amallard/cplusplus3/blob/master/binary-tree/BinaryTree.h ) to practice recursion. Yes, there’s not much of a “point” to the exercise, but it should be relatively easy to understand what you need to do and useful practice for the final exam.
Requirements:
Override the == operator to compare 2 trees – return true if the trees have the same values in the same positions. In particular, a tree with the values 1 and 2 with 1 at the root will be considered different from a tree with the values 1 and 2, but with 2 at the root.
For both this and the minimum function below, you should follow the pattern of a public function for the requirement, plus a private recursive function that does the work.
Note that the recursive function that does the work does not have to be ==. (If you want to override == to handle the recursion, note that you will need to override == for TreeNode.) It can just be a recursive function like insert() or deleteNode().
Implement a function minimum that does not take any parameters and returns the smallest value in the tree – the return type depends on the type of element of the tree. While you could write a non-recursive version of this, for this assignment you are required to write a recursive version. Note that there is a “max” function in the code that does something very different, so don’t try to use that as a model for this function.
Write a driver to test the above 2 functions.
Implement a couple operations for the binary search tree code from Allard (https://github.com/Amallard cphusplus3 blob masterbinary tree BinaryTree.h) to practice recursion. Yes, there's not much of a"point" to the exercise, but it should be relatively easy to understand what you need to do and useful practice for the final exam. Requirement:s: 1. Override the-operator to compare 2 trees-return true if the trees have the same values in the same positions. In particular, a tree with the values 1 and 2 with 1 at the root will be considered different from a tree with the values1 and 2 but with 2 at the root. .For both this and the minimum function below, you should follow the pattern of a public function for the requirement, plus a private recursive function that does the work Note that the recursive function that does the work does not have to be.(Ifyou want to overidto handle the recursion, note that you will need to override for TreeNode.) It can just be a recursive function like insert0) or 2. Implement a function minimum that does not take any parameters and returns the smallest value in the tree-the return type depends on the type of element of the tree. While you could write anon-recursive version of this, for this assignment you are required to write a recursive version. Note that there is a "max" function in the code that does something very different, so don't try to use that as a model for this function. 3. Write a driver to test the above 2 functions. Grading -30% minimum) 30% driver 20% Comments count for 10%; something for each file class, something for each method function other comments to explain parts of the code when it's not clear Choosing appropriate names for variables, functions, constants, classes counts for 10% . .Explanation / Answer
Below is the modified version of BinaryTree.h . Original file taken from github source in the question.
"==" operator has been overloaded and a recursive function "matchingTrees" is used to compare two trees.
findMinNode function finds the node with the minimum value in a binary tree.
#ifndef BINARYTREE_H
#define BINARYTREE_H
#include <iostream>
using namespace std;
/***********************************
Class BinaryTree.h - This class is a template binary tree class. It has methods to insert, remove, search,
display in order, display pre order, display post order, count the total number of items, count how many
items are on the left side, and count how many levels are in the tree.
Author: Adam Allard
Created: 05/06/15
Revisions: 05/07/15 - Added the countNodes(), countLeftNodes(), and countTreeHeight()
methods from the BinaryTree class
***********************************/
template <class T>
class BinaryTree
{
private:
struct TreeNode
{
T value;
TreeNode *left;
TreeNode *right;
friend bool operator==(TreeNode const & lhs, TreeNode const & rhs)
{
return *lhs == *rhs->value
&& ((lhs->left == 0 && rhs->left == 0)
|| (lhs->left != 0 && rhs->left != 0 && lhs->left->value == rhs->left->value))
&& ((lhs->right == 0 && rhs->right == 0)
|| (lhs->right != 0 && rhs->right != 0 && lhs->right->value == rhs->right->value));
}
};
TreeNode *root;
int totalNodes;
int leftNodes;
int treeHeight;
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 countNodes(TreeNode *);
int countLeftNodes(TreeNode *);
int countTreeHeight(TreeNode *);
int max(T, T);
public:
BinaryTree()
{ root = nullptr; }
~BinaryTree()
{ destroySubTree(root); }
void insertNode(T);
bool searchNode(T);
void remove(T);
void displayInOrder() const
{ displayInOrder(root); }
void displayPreOrder() const
{ displayPreOrder(root); }
void displayPostOrder() const
{ displayPostOrder(root); }
int countNodes()
{
countNodes(root);
return totalNodes;
}
int countLeftNodes()
{
countLeftNodes(root->left);
return leftNodes;
}
int countTreeHeight()
{
countTreeHeight(root);
return treeHeight;
}
//void operator==(const BinaryTree& originalTree);
};
// private method
template <class T>
void BinaryTree<T>::insert(TreeNode *&nodePtr, TreeNode *&newNode)
{
if (!nodePtr)
nodePtr = newNode;
else if (newNode->value < nodePtr->value)
insert(nodePtr->left, newNode);
else
insert(nodePtr->right, newNode);
}
// public method - user interacts
template <class T>
bool BinaryTree<T>::operator==(const BinaryTree& otherTree) const
{
return matchingTrees(otherTree);
}
template <class T>
int BinaryTree<T>::matchingTrees(const BinaryTree& otherTree)
{
flag = false;
if (root == NULL && otherTree.root == NULL)
return(flag);
if (root != NULL && otherTree.root != NULL)
{
return
(
*root == *otherTree.root &&
matchingTrees(root->left, otherTree.root->left) &&
matchingTrees(root->right, otherTree.root->right)
);
}
else
{
return(flag);
}
}
template <class T>
int BinaryTree<T>::findMinNode(TreeNode *root)
{
int minsofar = *root;
if (root->left != NULL)
{
minsofar = std::min(least, min(root->left));
}
if (root->right != NULL)
{
minsofar = std::min(least, min(root->right));
}
return minsofar;
}
}
template <class T>
void BinaryTree<T>::insertNode(T item)
{
TreeNode *newNode = nullptr;
newNode = new TreeNode;
newNode->value = item;
newNode->left = newNode->right = nullptr;
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;
}
// public method - user interacts
template <class T>
void BinaryTree<T>::remove(T item)
{
deleteNode(item, root);
}
// private method
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);
}
// private method
template <class T>
void BinaryTree<T>::makeDeletion(TreeNode *&nodePtr)
{
TreeNode *tempNodePtr = nullptr;
if (!nodePtr)
cout << "Cannot delete empty node." << endl;
else if (!nodePtr->right)
{
tempNodePtr = nodePtr;
nodePtr = nodePtr->left;
delete tempNodePtr;
}
else if (!nodePtr->left)
{
tempNodePtr = nodePtr;
nodePtr = nodePtr->right;
delete tempNodePtr;
}
else
{
tempNodePtr = nodePtr->right;
while (tempNodePtr->left)
{
tempNodePtr = tempNodePtr->left;
}
tempNodePtr->left = nodePtr->left;
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 << endl;
displayInOrder(nodePtr->right);
}
}
template <class T>
void BinaryTree<T>::displayPreOrder(TreeNode *nodePtr) const
{
if (nodePtr)
{
cout << nodePtr->value << endl;
displayPreOrder(nodePtr->left);
displayPreOrder(nodePtr->right);
}
}
template <class T>
void BinaryTree<T>::displayPostOrder(TreeNode *nodePtr) const
{
if (nodePtr)
{
displayPostOrder(nodePtr->left);
displayPostOrder(nodePtr->right);
cout << nodePtr->value << endl;
}
}
// count the total number of nodes in tree
template <class T>
int BinaryTree<T>::countNodes(TreeNode *nodePtr)
{
if (!nodePtr)
return 0;
else
{
totalNodes++;
countNodes(nodePtr->left);
countNodes(nodePtr->right);
}
}
// count the number of nodes in left subtree
template <class T>
int BinaryTree<T>::countLeftNodes(TreeNode *nodePtr)
{
if (!nodePtr)
return 0;
else
{
leftNodes++;
countLeftNodes(nodePtr->left);
if (nodePtr != root)
countLeftNodes(nodePtr->right);
}
}
// count how many levels the tree is
template <class T>
int BinaryTree<T>::countTreeHeight(TreeNode *nodePtr)
{
if (!nodePtr)
return 0;
else
{
treeHeight = max(countTreeHeight(nodePtr->left), countTreeHeight(nodePtr->right)) + 1;
return treeHeight;
}
}
// private function used for the countTreeHeight method
template <class T>
int BinaryTree<T>::max(T x, T y)
{
if (x > y)
return x;
else
return y;
}
#endif
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.