BST Class Completion Using bst.h under BST_v3 in the course Dropbox folder, complete the BST class by adding the following: A copy constructor. An assignment operator overload. A public remove function to remove a node with a given key. The additions to the class should take the following form: template class BST { public: BST(const BST& t); BST& operator=(const BST& t); void remove(const K& k); }; A test program is provided in the above mentioned folder named bst-test.cpp. A loop for calling the remove function is commented out; be sure to un-comment this loop for testing. When coding the remove function, keep in mind that the given key might not exist in the tree, in which case the remove function should do nothing. Also, you should think about addressing the easier cases first, such as: The given key is not found (very easy). The root node is to be deleted, and it is the only node in the tree. The node to be delete is a leaf node. Once you have addressed the easy cases, move on to removal of other nodes. When you turn in this assignment, submit only your modified bst.h file. Document your code with comments to explain your approach, especially your logic for node removal. No accompanying written work is required for this assignment.

###__________Header File___________________###

#pragma once

template

class BST {

protected:

class Node {

public:

Node(const K& k, const T& d, Node* p)

{ key = k; data = d; left = right = nullptr; parent = p; }

K key;

T data;

Node *left;

Node *right;

Node *parent;

};

Node *root;

void destroy(Node *p);

T& get(Node *p, const K& k);

bool insert(Node *p, const K& k, const T& d);

template

void inorder(Node *p, U& fcn) const {

if (p) {

inorder(p->left, fcn);

fcn(p->key, p->data);

inorder(p->right, fcn);

}

}

public:

BST() { root = nullptr; }

virtual ~BST() { destroy(root); }

T& get(const K& k) { return get(root, k); }

bool insert(const K& k, const T& d);

T& operator[](const K& k) { return get(k); }

template

U inorder(U fcn) const { inorder(root, fcn); return fcn; }

};

template

void BST::destroy(Node* p) {

if (p) {

destroy(p->left);

destroy(p->right);

delete p;

}

}

template

T& BST::get(Node *p, const K& k) {

// If key matches, return data item

if (k == p->key)

return p->data;

// Left side?

if (k < p->key) {

if (!p->left)

insert(p, k, T());

return get(p->left, k);

}

// Right side.

if (!p->right)

insert(p, k, T());

return get(p->right, k);

}

template

bool BST::insert(const K& k, const T& d) {

if (root)

return insert(root, k, d);

root = new Node(k, d, nullptr);

return true;

}

template

bool BST::insert(Node *p, const K& k, const T& d) {

// If key matches node's key, cannot insert

if (k == p->key)

return false;

// Insert into left sub-tree?

if (k < p->key) {

if (p->left)

return insert(p->left, k, d);

p->left = new Node(k, d, p);

return true;

}

// Insert into right sub-tree.

if (p->right)

return insert(p->right, k, d);

p->right = new Node(k, d, p);

return true;

}

###_______Test Program_______________###

#include "bst.h"

#include

#include

#include

#include

#include

using namespace std;

// Testing class derived from BST that includes a pre-order traversal

template

class BSTTest : public BST {

protected:

template

void preorder (Node* p, U& fcn, int depth) const {

if (p) {

fcn(p->key, p->data, depth);

preorder(p->left, fcn, depth + 1);

preorder(p->right, fcn, depth + 1);

}

}

public:

template

U preorder (U fcn) const { preorder(root, fcn, 0); return fcn; }

};

// For use with pre-order traversal, prints tree showing depth of each node

void print_depth (int k, int v, int d) {

for (int i = 0; i < d; i++)

cout << "-";

cout << k << ": " << v << endl;

}

// For printing list of keys

void print_int (int n) { cout << " " << n; }

// Used with inorder traversal to generate list of random keys

class random_keys {

public:

list keys;

void operator() (int k, int v) {

if (rand() % 2)

keys.push_back(k);

}

};

int main () {

BSTTest t;

srand(time(0));

// Populate list with 16 random key/value pairs

for (int i = 0; i < 16; i++)

while (!t.insert(rand() % 90 + 10, rand()));

// Show pre-order traversal of the tree

t.preorder(print_depth);

// Generate list of random keys to be removed from the tree

list keys = t.inorder(random_keys()).keys;

cout << "Remove:";

for_each(keys.begin(), keys.end(), print_int);

cout << endl;

// Make copy of t using copy contrustor

BSTTest t2(t);

// Remove keys

// for (list::iterator i = keys.begin(); i != keys.end(); i++)

// t2.remove(*i);

// Show pre-order traversal of the copy (should have keys removed)

t2.preorder(print_depth);

// Make another copy of t and test assignment operator

BSTTest t3(t);

t3 = t2;

// Show pre-order traversal of copy (should be same as t2)

t3.preorder(print_depth);

#ifdef _MSC_VER

system("pause");

#endif

return 0;

}