In this assignment, you will implement the following inorder, preorder, and post
ID: 3823740 • Letter: I
Question
In this assignment, you will implement the following inorder, preorder, and postorder traversal functions on a binary search tree:
Each of these traversal methods matches a public method that takes a function pointer as a parameter with an overloaded private method that takes a function pointer and a binary-search-tree node pointer as parameters. The private method is recursive. The reason the matching of public and private functions is necessary is that the private function takes a node pointer in the second parameter position; node pointers are private to the binary search tree.
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.
Here is an example: suppose you have the following BST:
BST.inOrder(); yields 14->21->24->25->28->31->32->36->39->41->47
BST.preOrder(); yields 32->24->21->14->28->25->31->41->36->39->47
BST.postOrder(); yields 14->21->25->31->28->24->39->36->47->41->32
bst.h:
#pragma once
#include
#include
namespace cs20a
{
template class bst;
template
class bst_node {
friend class bst;
private:
T value;
bst_node *left, *right, *parent;
bst_node() : value(), left(nullptr), right(nullptr), parent(nullptr) {}
bst_node(const T& t, bst_node *left = nullptr, bst_node *right = nullptr, bst_node *parent = nullptr)
: value(t), left(left), right(right), parent(parent) {};
};
template
class bst {
public:
bst();
bst(const bst &rhs);
~bst();
bst& operator =(const bst & rhs);
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();
//*** Implement these functions
void inOrder(void(*func)(const T &) = nullptr) const;
void preOrder(void(*func)(const T &) = nullptr) const;
void postOrder(void(*func)(const T &) = nullptr) const;
//***
private:
bst_node *root;
size_t _size;
void init();
void makeEmpty(bst_node* node);
void copy(const bst_node* node);
void insert(const T & value, bst_node* node);
void remove(const T & value, bst_node* node);
bool contains(const T& value, bst_node* node) const;
T & retrieve(T & value, bst_node* node) const;
void print(bst_node* node, size_t level) const;
//*** Implement these functions
void inOrder(void(*func)(const T &), bst_node* node) const;
void preOrder(void(*func)(const T &), bst_node* node) const;
void postOrder(void(*func)(const T &), bst_node* node) const;
//***
bst_node * findNode(const T &) const;
bst_node * findNode(const T &, bst_node* node) const;
bst_node * findParentNode(bst_node* node) const;
bst_node * findParentNode(bst_node* node, bst_node* child, bst_node* parent) const;
bst_node * getMaxNode(bst_node* node) const;
bst_node * getMinNode(bst_node* node) const;
};
template
bst::bst() {
init();
}
template
bst::bst(const bst &rhs) {
init();
copy(rhs.root);
}
template
bst& bst::operator=(const bst& rhs) {
if (this != &rhs) {
clear();
copy(rhs.root);
}
return *this;
}
template
bst::~bst() {
makeEmpty(root);
}
template
bool bst::empty() const {
return root == nullptr;
}
template
void bst::clear() {
makeEmpty(root);
init();
}
template
size_t bst::size() const {
return _size;
}
template
void bst::copy(const bst_node* node) {
if (node != NULL)
insert(node->value);
if (node->left != NULL)
copy(node->left);
if (node->right != NULL)
copy(node->right);
}
template
void bst::makeEmpty(bst_node* node) {
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::init() {
root = nullptr;
_size = 0;
}
template
void bst::insert(const T &value) {
if (root == nullptr)
{
root = new bst_node(value, nullptr, nullptr, nullptr);
_size++;
}
else
{
insert(value, root);
}
}
template
void bst::insert(const T &value, bst_node* node) {
if (value < node->value)
{
if (node->left == nullptr)
{
node->left = new bst_node(value, nullptr, nullptr, node);
_size++;
}
else
{
insert(value, node->left);
}
}
else
if (value > node->value)
{
if (node->right == nullptr)
{
node->right = new bst_node(value, nullptr, nullptr, node);
_size++;
}
else
{
insert(value, node->right);
}
}
}
template
void bst::remove(const T &value) {
if (root != nullptr)
remove(value, root);
}
template
void bst::remove(const T &value, bst_node* node) {
bst_node* current = findNode(value, node);
if (current == nullptr)
return;
bst_node* parent = findParentNode(current);
// Case 1: node to be deleted has no children
if (current->left == nullptr && current->right == nullptr)
{
if (parent != nullptr)
{
if (current->value < parent->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 < parent->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 < parent->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* maxNode = getMaxNode(current->left);
bst_node* maxParentNode = findParentNode(maxNode);
current->value = maxNode->value;
// Delete maxNode: right pointer is nullptr
if (maxParentNode != nullptr)
{
if (maxNode->left != nullptr)
maxNode->left->parent = maxParentNode;
if (maxNode->value < maxParentNode->value)
maxParentNode->left = maxNode->left;
else
maxParentNode->right = maxNode->left;
}
delete maxNode;
_size--;
}
else
{
return;
}
}
template
bst_node * bst::findNode(const T &value) const {
return findNode(value, root);
}
template
bst_node * bst::findNode(const T &value, bst_node* node) const {
if (node == nullptr)
return nullptr;
else if (value < node->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::findParentNode(bst_node* node) const {
bst_node *parent = nullptr;
bst_node *child = root;
return findParentNode(node, child, parent);
}
template
bst_node * bst::findParentNode(bst_node* node, bst_node* child, bst_node* parent) const {
if (child == nullptr)
return nullptr;
else if (node->value < child->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::retrieve(T &value) const {
return retrieve(value, root);
}
template
T & bst::retrieve(T &value, bst_node* node) const {
if (node == nullptr)
throw std::logic_error("Node does not exist.");
else if (value < node->value)
return retrieve(value, node->left);
else if (value > node->value)
return retrieve(value, node->right);
else
return node->value;
}
template
void bst::print()
{
size_t indent = 0;
print(root, indent);
}
template
void bst::print(bst_node* node, size_t level) const
{
if (node != nullptr)
{
print(node->left, level + 1);
cout << std::string(level * 4, '-') << node->value << endl;
print(node->right, level + 1);
}
}
template
bool bst::contains(const T &value) const {
if (root == nullptr)
return false;
else
return contains(value, root);
}
template
bool bst::contains(const T &value, bst_node *node) const {
if (node == nullptr)
return false;
else if (value < node->value)
return contains(value, node->left);
else if (value > node->value)
return contains(value, node->right);
else // value == node->value
return true;
}
template
void bst::inOrder(void(*func)(const T &)) const {
}
template
void bst::inOrder(void(*func)(const T &), bst_node* node) const {
}
template
void bst::preOrder(void(*func)(const T &)) const {
}
template
void bst::preOrder(void(*func)(const T &), bst_node* node) const {
}
template
void bst::postOrder(void(*func)(const T &)) const {
}
template
void bst::postOrder(void(*func)(const T &), bst_node* node) const {
}
template
bst_node * bst::getMaxNode(bst_node* node) const {
if (node == nullptr)
return node;
if (node->right != nullptr)
return getMaxNode(node->right);
else
return node;
}
template
bst_node * bst::getMinNode(bst_node* node) const {
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, OTHER };
CHOICE menu();
int main(int argc, char* argv[]) {
int value;
bst bst;
CHOICE choice;
do {
choice = menu();
switch (choice) {
case MAKEEMPTY:
bst.clear();
break;
case ISEMPTY:
if (bst.empty()) {
cout << "Tree is empty." << endl;
}
else {
cout << "Tree is not empty." << endl;
}
break;
case REMOVE:
if (bst.empty())
cout << "Empty tree." << endl;
else
cout << "Please provide int to remove: ";
cin >> value;
bst.remove(value);
break;
case INSERT:
cout << "Please provide int to insert: ";
cin >> value;
bst.insert(value);
break;
case PRINT:
bst.print();
cout << endl;
break;
case INORDER:
cout << "InOrder Traversal:" << endl;
bst.inOrder(printValue);
break;
case PREORDER:
cout << "PreOrder Traversal:" << endl;
bst.preOrder(printValue);
break;
case POSTORDER:
cout << "PostOrder Traversal:" << endl;
bst.postOrder(printValue);
break;
case OTHER:
cout << "Not a valid choice." << endl;
break;
}
} while (choice != QUIT);
return(0);
}
CHOICE menu() {
char choice;
CHOICE result;
cout << "(M)akeEmpty Is(E)mpty (I)nsert (R)emove (P)rint (1) InOrder (2) PreOrder (3) PostOrder (Q)uit: " << endl;
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 '1':
result = INORDER;
break;
case '2':
result = PREORDER;
break;
case '3':
result = POSTORDER;
break;
default:
result = OTHER;
break;
}
return(result);
}
void printValue(const int & value)
{
cout << value << endl;
}
public: void inorder (void(* func const T &) const void preorder (void(* func const T &)) const void postorder (void func const T &)) const private: void inorder (void func const T &) bst node KT node const void reorder (void(* func const T &) bst node KT node const void postorder (void *func) (const T &), bst node node const KTExplanation / Answer
template
void bst::inOrder(void(*func)(const T &)function) const {
inOrder(function, root)
}
template
void bst::inOrder(void(*func)(const T &)function, bst_node* node) const {
if (node == nullptr)
return;
/* first recur on left child */
inOrder(function,node->left);
/* then print the data of node */
function(node->value);
/* now recur on right child */
inOrder(function, node->right);
}
template
void bst::preOrder(void(*func)(const T &)function) const {
preOrder(function, root);
}
template
void bst::preOrder(void(*func)(const T &)function, bst_node* node) const {
if (node == nullptr)
return;
/* then print the data of node */
function(node->value);
/* first recur on left child */
preOrder(function,node->left);
/* now recur on right child */
preOrder(function, node->right);
}
template
void bst::postOrder(void(*func)(const T &)function) const {
postOrder(function, root);
}
template
void bst::postOrder(void(*func)(const T &)function, bst_node* node) const {
if (node == nullptr)
return;
/* first recur on left child */
postOrder(function,node->left);
/* now recur on right child */
postOrder(function, node->right);
/* then print the data of node */
function(node->value);
}