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); };

::The code::

#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;

}