Question: In this assignment, you will create a new method called closestValue() that takes a value as an argument and then locates the value in the
In this assignment, you will create a new method called closestValue() that takes a value as an argument and then locates the value in the binary search tree (BST) that is closest to that argument. If the root of the tree is NULL, your method should throw an exception. You may not use an iterator for this assignment.
T BST::closestValue(T value);
For example, consider the following BST:
closestValue(10) should return 14. closestValue (20) should return 21. closestValue(42) should return 41.
HINT: The value returned will come from the nodes found on the path followed, as if the parameter is getting inserted into the tree.
HINT: Use recursion and pass additional parameters to keep track of the closest value you have seen so far. Pass this closest value by reference so that future recursive calls can update the parameter as additional nodes are encountered.
Do not alter the class definition or driver code in any way. Programs that crash are subject to a 50% penalty. Please submit the class header file only (bst.h). PLEASE NOTE: You may not use any Standard Template Library (STL) classes for this assignment; use code provided below only.
Please make sure to compile your code and check for errors before submitting code that is not working.
bst.h:
#pragma once
#include
#include
#include
#include
namespace cs20a
{
using namespace std;
template
template
class bst_node {
friend class bst
private:
T value;
bst_node
bst_node() : value(), left(nullptr), right(nullptr), parent(nullptr) {}
bst_node(const T& t, bst_node
: value(t), left(left), right(right), parent(parent) {};
};
template
class bst {
public:
bst();
bst(const bst
~bst();
bst
bool empty() const;
void clear();
size_t size() const;
void insert(const T & value);
void remove(const T & value);
bool contains(const T & value) const;
T & retrieve(T & value) const;
void print();
void inOrder(void(*func)(const T &) = nullptr) const;
//*** Implement this function
T closestValue(T value) const;
private:
bst_node
size_t _size;
void init();
void makeEmpty(bst_node
void copy(const bst_node
void insert(const T & value, bst_node
void remove(const T & value, bst_node
bool contains(const T& value, bst_node
T & retrieve(T & value, bst_node
void print(bst_node
void inOrder(void(*func)(const T &), bst_node
bst_node
bst_node
bst_node
bst_node
bst_node
bst_node
//*** Implement this function
T closestValue(T value, T & closest, bst_node
};
template
bst
init();
}
template
bst
init();
copy(rhs.root);
}
template
bst
if (this != &rhs) {
clear();
copy(rhs.root);
}
return *this;
}
template
bst
makeEmpty(root);
}
template
bool bst
return root == nullptr;
}
template
void bst
makeEmpty(root);
init();
}
template
size_t bst
return _size;
}
template
void bst
if (node != NULL)
insert(node->value);
if (node->left != NULL)
copy(node->left);
if (node->right != NULL)
copy(node->right);
}
template
void bst
if (node != NULL) {
if (node->left != NULL)
makeEmpty(node->left);
if (node->right != NULL)
makeEmpty(node->right);
delete node;
node = NULL;
_size--;
}
}
template
void bst
root = nullptr;
_size = 0;
}
template
void bst
if (root == nullptr)
{
root = new bst_node
_size++;
}
else
{
insert(value, root);
}
}
template
void bst
if (value value)
{
if (node->left == nullptr)
{
node->left = new bst_node
_size++;
}
else
{
insert(value, node->left);
}
}
else
if (value > node->value)
{
if (node->right == nullptr)
{
node->right = new bst_node
_size++;
}
else
{
insert(value, node->right);
}
}
}
template
void bst
if (root != nullptr)
remove(value, root);
}
template
void bst
bst_node
if (current == nullptr)
return;
bst_node
// Case 1: node to be deleted has no children
if (current->left == nullptr && current->right == nullptr)
{
if (parent != nullptr)
{
if (current->value value)
parent->left = nullptr;
else
parent->right = nullptr;
}
delete current;
_size--;
}
// Case 2: node to be deleted has one child
else if (current->left != nullptr && current->right == nullptr)
{
if (parent != nullptr)
{
current->left->parent = parent;
if (current->value value)
parent->left = current->left;
else
parent->right = current->left;
}
delete current;
_size--;
}
else if (current->left == nullptr && current->right != nullptr)
{
if (parent != nullptr)
{
current->right->parent = parent;
if (current->value value)
parent->left = current->right;
else
parent->right = current->right;
}
delete current;
_size--;
}
// Case 3: node to be deleted has two children
else if (current->left != nullptr && current->right != nullptr)
{
bst_node
bst_node
current->value = maxNode->value;
// Delete maxNode: right pointer is nullptr
if (maxParentNode != nullptr)
{
if (maxNode->left != nullptr)
maxNode->left->parent = maxParentNode;
if (maxNode->value value)
maxParentNode->left = maxNode->left;
else
maxParentNode->right = maxNode->left;
}
delete maxNode;
_size--;
}
else
{
return;
}
}
template
bst_node
return findNode(value, root);
}
template
bst_node
if (node == nullptr)
return nullptr;
else if (value value)
return findNode(value, node->left);
else if (value > node->value)
return findNode(value, node->right);
else // value == node->value
return node;
}
template
bst_node
bst_node
bst_node
return findParentNode(node, child, parent);
}
template
bst_node
if (child == nullptr)
return nullptr;
else if (node->value value)
{
parent = child;
return findParentNode(node, child->left, parent);
}
else if (node->value > child->value)
{
parent = child;
return findParentNode(node, child->right, parent);
}
else // child == node
return parent;
}
template
T & bst
return retrieve(value, root);
}
template
T & bst
if (node == nullptr)
throw std::logic_error("Node does not exist.");
else if (value value)
return retrieve(value, node->left);
else if (value > node->value)
return retrieve(value, node->right);
else
return node->value;
}
template
void bst
{
size_t indent = 0;
print(root, indent);
}
template
void bst
{
if (node != nullptr)
{
print(node->left, level + 1);
cout value
print(node->right, level + 1);
}
}
template
bool bst
if (root == nullptr)
return false;
else
return contains(value, root);
}
template
bool bst
if (node == nullptr)
return false;
else if (value value)
return contains(value, node->left);
else if (value > node->value)
return contains(value, node->right);
else // value == node->value
return true;
}
//*** Implement these functions
template
T bst
{
return T();
}
template
T bst
{
}
//***
template
void bst
inOrder(func, root);
}
template
void bst
if (node != nullptr)
{
inOrder(func, node->left);
if (func != nullptr)
func(node->value);
inOrder(func, node->right);
}
}
template
bst_node
if (node == nullptr)
return node;
if (node->right != nullptr)
return getMaxNode(node->right);
else
return node;
}
template
bst_node
if (node == nullptr)
return node;
if (node->left != nullptr)
return getMinNode(node->left);
else
return node;
}
}
BSTMenu.cpp:
#include
#include "bst.h"
using namespace std;
using namespace cs20a;
void printValue(const int &value);
enum CHOICE { MAKEEMPTY, ISEMPTY, INSERT, REMOVE, QUIT, PRINT, INORDER, PREORDER, POSTORDER, CLOSESTVALUE, OTHER };
CHOICE menu();
int main(int argc, char* argv[]) {
int value;
bst
CHOICE choice;
do {
choice = menu();
switch (choice) {
case MAKEEMPTY:
bst.clear();
break;
case ISEMPTY:
if (bst.empty()) {
cout
}
else {
cout
}
break;
case REMOVE:
if (bst.empty())
cout
else
cout
cin >> value;
bst.remove(value);
break;
case INSERT:
cout
cin >> value;
bst.insert(value);
break;
case PRINT:
bst.print();
cout
break;
case INORDER:
cout
bst.inOrder(printValue);
break;
case CLOSESTVALUE:
cout
cin >> value;
cout
break;
case OTHER:
cout
break;
}
} while (choice != QUIT);
return(0);
}
CHOICE menu() {
char choice;
CHOICE result;
cout
cin >> choice;
switch (choice) {
case 'M':
case 'm':
result = MAKEEMPTY;
break;
case 'E':
case 'e':
result = ISEMPTY;
break;
case 'I':
case 'i':
result = INSERT;
break;
case 'Q':
case 'q':
result = QUIT;
break;
case 'R':
case 'r':
result = REMOVE;
break;
case 'P':
case 'p':
result = PRINT;
break;
case 'O':
case 'o':
result = INORDER;
break;
case 'C':
case 'c':
result = CLOSESTVALUE;
break;
default:
result = OTHER;
break;
}
return(result);
}
void printValue(const int & value)
{
cout
}
14 21 24 28 32 31 36 41 39 47
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help