C$++$ PLEASE

$21\mathrm{.}14$ CIST$2362$ Lab: Binary Search Tree $($BST$)$ Containe

This lab is about building a simple Binary Search Tree Container. Your tasks are to complete the following member functions for the Tree class:

void insert$($const T&$)$: This function inserts a new value into the BST

TreeNode$*$ find$($const T&$)$: This function performs a BST search to determine if a value exists in the binary tree

void outputTree$()$: This function outputs "Tree Empty" if there are no nodes in the tree. This function also uses a recursive helper function when there are nodes in the tree: void outputTreeHelper$($TreeNode$*)$

void outputTreeHelper$($TreeNode$*)$: This is a recursive function that traverses the BST in$-$order.

You should use the pseudo$-$code in the chapter to provide guidance in writing each of these functions.

The main$()$ that is provided is a sample main that you can use to test class. When you submit, you will only be submitting the Tree.h file. The program expects to read a file of words and then inserts them into the BST$.$ The file may look like:

highway

difference

philosophy

quality

agency

The output for this input would be:

size of tree: $5$

agency

difference

highway

philosophy

quality

MAIN.CPP

#include

#include

#include

#include "Tree.h$"$

int main$()\{$

Tree treeOfStrings;

std::ifstream inputFile;

std::string filename;

std::string inputData;

std::cin $>>$ filename;

inputFile.open$($filename$)$;

while $($inputFile $>>$ inputData$)\{$

treeOfStrings.insert$($inputData$)$;

$\}$

std::cout $$ "size of tree: $"$ treeOfStrings.size$()$ std::endl;

treeOfStrings.outputTree$()$;

return $0$;

$\}$

TREENODE.H

#ifndef LAB$\_\_\_$LESSON$\_13\_\_\_$TREES$\_$TREENODE$\_$H

#define LAB$\_\_\_$LESSON$\_13\_\_\_$TREES$\_$TREENODE$\_$H

template

class TreeNode $\{$

private:

T dataItem;

TreeNode$*$ left;

TreeNode$*$ right;

protected:

public:

TreeNode$($T dataItem, TreeNode $*$left $=$ nullptr, TreeNode $*$right $=$ nullptr$)$ :

dataItem$($dataItem$),$ left$($left$),$ right$($right$)\{\}$

T getDataItem$()$ const;

void setDataItem$($T dataItem$)$;

TreeNode $*$getLeft$()$ const;

void setLeft$($TreeNode $*$left$)$;

TreeNode $*$getRight$()$ const;

void setRight$($TreeNode $*$right$)$;

$\}$;

template

T TreeNode::getDataItem$()$ const $\{$

return dataItem;

$\}$

template

void TreeNode::setDataItem$($T dataItem$)\{$

TreeNode::dataItem $=$ dataItem;

$\}$

template

TreeNode $*$TreeNode::getLeft$()$ const $\{$

return left;

$\}$

template

void TreeNode::setLeft$($TreeNode $*$left$)\{$

TreeNode::left $=$ left;

$\}$

template

TreeNode $*$TreeNode::getRight$()$ const $\{$

return right;

$\}$

template

void TreeNode::setRight$($TreeNode $*$right$)\{$

TreeNode::right $=$ right;

$\}$

#endif $//$LAB$\_\_\_$LESSON$\_13\_\_\_$TREES$\_$TREENODE$\_$H

TREE.H

#ifndef LAB$\_\_\_$LESSON$\_13\_\_\_$TREES$\_$TREE$\_$H

#define LAB$\_\_\_$LESSON$\_13\_\_\_$TREES$\_$TREE$\_$H

#include

#include "TreeNode.h$"$

template

class Tree $\{$

private:

TreeNode$*$ root;

unsigned int currentSize;

void outputTreeHelper$($TreeNode$*$ node$)$;

protected:

public:

explicit Tree$($TreeNode $*$root $=$ nullptr$)$ : root$($root$),$ currentSize$(0)\{\}$

TreeNode $*$getRoot$()$ const;

unsigned int size$()$ const;

void insert$($const T&$)$;

TreeNode$*$ find$($const T&$)$;

void outputTree$()$;

$\}$;

template

TreeNode $*$Tree::getRoot$()$ const $\{$

return root;

$\}$

template

void Tree::insert$($const T& dataItem$)\{$

$//$ TODO: Complete this function

$\}$

template

TreeNode$*$ Tree::find$($const T& lookfor$)\{$

$//$ TODO: Complete this function

return nullptr; $//$ Not found

$\}$

template

void Tree::outputTree$()\{$

if $($root $==$ nullptr$)\{$

$//$ TODO: Complete code here

$\}$ else $\{$

$//$ TODO: Complete code here

$\}$

$\}$

template

void Tree::outputTreeHelper$($TreeNode$*$ node$)\{$

$//$ TODO: Complete this function

$\}$

template

unsigned int Tree::size$()$ const $\{$

return currentSize;

$\}$

#endif $//$LAB$\_\_\_$LESSON$\_13\_\_\_$TREES$\_$TREE$\_$H

EXPERT ANSWER NEED EDIT. CODE IS RIGHT JUST NEED LINESPACING EDIT.

PLEASE PROVIDE LINESPACING EDIT FOR THIS NEW CODE OF TREE.H IN C$++$

#ifndef LAB$\_$LESSON$\_1\_3\_$TREES$\_$TREE$\_$H

#define LAB$\_$LESSON$\_1\_3\_$TREES$\_$TREE$\_$H

#include

#include "TreeNode.h$"$

$//$ Template class for a Binary Search Tree $($BST$)$

template

class Tree $\{$

private:

TreeNode$*$ root; $//$ Pointer to the root node of the tree

unsigned int currentSize; $//$ Number of nodes in the tree

$//$ Recursive helper function to output the tree in$-$order

void outputTreeHelper$($TreeNode$*$ node$)\{$

if $($node $!=$ nullptr$)\{$

outputTreeHelper$($node$->$getLeft$())$;

std::cout $$ node$->$getDataItem;

outputTreeHelper$($node$->$getRight$())$;

$\}$

$\}$

protected:

public:

$//$ Constructor for a new tree with an optional root node

explicit Tree$($TreeNode$*$ root $=$ nullptr$)$ : root$($root$),$ currentSize$(0)\{\}$

$//$ Getter for the root node of the tree

TreeNode$*$ getRoot$()$ const $\{$ return root; $\}$

$//$ Getter for the number of nodes in the tree

unsigned int size$()$ const $\{$ return currentSize; $\}$

$//$Output is nearly correct, but whi