#include "BinaryTreeNode.h$"$

#include "BinaryTree.h$"$

#include "BSTree.h$"$

#include "iostream"

using namespace std;

int main$()$

$\{$

$//$To Do

$//$Write your code in the main$()$ function

$//$Do not use any global variables

cout $$ "Tree $1$:$"$ endl;

BSTree myBstTree;

return $0$;

$\}$

#pragma once

#include"BinaryTreeNode.h

$"$

$$

using namespace std;

template

class BSTree : public BinaryTree

$\{$

protected:

$$ BinaryTreeNode

$*$

$$root;

$/$

$/$

$$root of tree

public:

$$ BSTree

$($

$)$

$$: root

$($

NULL

$)$

$\{$

$\}$

;

$$ BSTree

$($

const BSTree&

$)$

;

$$ BSTree

$($

T data

$)$

$\{$

$$root

$=$

$$new BinaryTreeNode

$($

data

$)$

;

$\}$

;

$$ virtual ~BSTree

$($

$)$

$\{$

$$if

$($

root

$)$

$$delete root;

$\}$

;

$$ BinaryTreeNode

$*$

$$getRoot

$($

$)$

$\{$

$$ return root;

$$

$\}$

$$ T findSmallest

$($

BinaryTreeNode

$*$

$$nodep

$)$

;

$$ virtual bool insert

$($

BinaryTreeNode

$*$

$$nodep$,$ const T& x

$)$

;

$$ virtual const T

$*$

$$const search

$($

BinaryTreeNode

$*$

$$nodep$,$ const T& x

$)$

;

$$ virtual bool remove

$($

BinaryTreeNode

$*$

$$nodep$,$ const T& x

$)$

;

$\}$

;

template

T BSTree::findSmallest

$($

BinaryTreeNode

$*$

$$nodep

$)$

$\{$

$$ if

$($

nodep

$-$

$>$

GetLeftChild

$($

$)$

$!$

$=$

$$nullptr

$)$

$\{$

$$ return findSmallest

$($

nodep

$-$

$>$

GetLeftChild

$($

$)$

$)$

;

$$

$\}$

$$

$/$

$/$

$$This is the data contained within the smallest node

$$ return nodep

$-$

$>$

GetData

$($

$)$

;

$\}$

template

const T

$*$

$$const BSTree::search

$($

BinaryTreeNode

$*$

$$nodep$,$ const T& x

$)$

$\{$

$$ if

$($

nodep

$=$

$=$

$0$

$)$

$\{$

$$ return NULL;

$$

$\}$

$$ if

$($

x

$=$

$=$

$$nodep

$-$

$>$

GetData

$($

$)$

$)$

$\{$

$$ return &

$($

nodep

$-$

$>$

GetData

$($

$)$

$)$

;

$$

$\}$

$$ if

$($

x

$$

$$nodep

$-$

$>$

GetData

$($

$)$

$)$

$\{$

$$ return search

$($

nodep

$-$

$>$

GetLeftChild

$($

$)$

$,$

$$x

$)$

;

$$

$\}$

$$ else

$\{$

$$ return search

$($

nodep

$-$

$>$

GetRightChild

$($

$)$

$,$

$$x

$)$

;

$$

$\}$

$\}$

template

bool BSTree::insert

$($

BinaryTreeNode

$*$

$$nodep$,$ const T& x

$)$

$\{$

$$

$/$

$/$

To Do: Write your code here

$\}$

template

bool BSTree::remove

$($

BinaryTreeNode

$*$

$$nodep$,$ const T& x

$)$

$\{$

$$

$/$

$/$

To Do: Write your code here

$\}$

You need to complete a BSTree

$($

Binary Search Tree

$)$

$$class in the BSTree.h file. In

particular, this class inherits from the BinaryTree class. Thus, the parent functions

such as

PreOrderTraverse

$($

BinaryTreeNodeYou need to complete a BSTree $($Binary Search Tree$)$ class in the BSTree.h file. In

particular, this class inherits from the BinaryTree class. Thus, the parent functions

such as

PreOrderTraverse$($BinaryTreeNode