In C++.

1. We need to be able to delete a node from a tree. A delete function to the tree class that takes a node value reference as a parameter and returns void. This function needs to delete the node and make certain to rearrange the tree so that it remains a valid binary search tree.

Code to add delete function to:

#pragma once

#include

#include

#include

using namespace std;

template

class Tree

{

struct Node

{

Node(std::shared_ptr const & lft

, T val

, std::shared_ptr const & rgt)

: _lft(lft), _val(val), _rgt(rgt)

{}

std::shared_ptr _lft;

T _val;

std::shared_ptr _rgt;

};

explicit Tree(std::shared_ptr const & node)

: _root(node) {}

unsigned int numberOfNodes = 0;

public:

Tree() {}

Tree(Tree const & lft, T val, Tree const & rgt)

: _root(std::make_shared(lft._root, val, rgt._root))

{

assert(lft.isEmpty() || lft.root() < val);

assert(rgt.isEmpty() || val < rgt.root());

}

Tree(std::initializer_list init) {

Tree t;

for (T v: init) {

t = t.insert(v);

}

_root = t._root;

}

bool isEmpty() const { return !_root; }

size_t size() { return numberOfNodes; }

T root() const {

assert(!isEmpty());

return _root->_val;

}

Tree left() const {

assert(!isEmpty());

return Tree(_root->_lft);

}

Tree right() const {

assert(!isEmpty());

return Tree(_root->_rgt);

}

Tree insert(T x) {

numberOfNodes++;

if (isEmpty())

return Tree(Tree(), x, Tree());

T y = root();

if (x < y)

return Tree(left().insert(x), y, right());

else if (y < x)

return Tree(left(), y, right().insert(x));

else

return *this; // no duplicates

}

bool member(T x) const {

if (isEmpty())

return false;

T y = root();

if (x < y)

return left().member(x);

else if (y < x)

return right().member(x);

else

return true;

}

bool find(T x, T &foundValue) const {

if (isEmpty())

return false;

T y = root();

if (x < y)

return left().member(x);

else if (y < x)

return right().member(x);

else {

foundValue = y;

return true;

}

}

void preorder(std::function visit) const {

if (isEmpty())

return;

T contents = root();

visit(contents);

left().preorder(visit);

right().preorder(visit);

}

void inorder(std::function visit) const {

if (isEmpty()) return;

left().inorder(visit);

T contents = root();

visit(contents);

right().inorder(visit);

}

void postorder(std::function visit) const {

if (isEmpty()) return;

left().postorder(visit);

right().postorder(visit);

T contents = root();

visit(contents);

}

private:

std::shared_ptr _root;

};