C++ help:

Implement the class BinarySearchTree, as given in listing 16-4

Driver program should:

-Insert 21 random numbers (1-100) on the tree

-Remove the last number inserted

-Display the tree. To display just use in order traversal

*No user input for driver program.

Use the BST ADT BinarySearchTree.h and the BinaryTreeInterface.h

BinarySearchTree.h code is shown below.

// Listing 16-4. /** Link-based implementation of the ADT binary search tree. @file BinarySearchTree.h */ #ifndef BINARY_SEARCH_TREE_ #define BINARY_SEARCH_TREE_ #include  #include "BinaryTreeInterface.h" #include "BinaryNode.h" #include "BinaryNodeTree.h" #include "NotFoundException.h" #include "PrecondViolatedExcep.h" template class BinarySearchTree : public BinaryNodeTree { private: std::shared_ptr> rootPtr; protected: //------------------------------------------------------------ // Protected Utility Methods Section: // Recursive helper methods for the public methods. //------------------------------------------------------------ // Recursively finds where the given node should be placed and // inserts it in a leaf at that point. auto placeNode(std::shared_ptr> subTreePtr, std::shared_ptr> newNode); // Removes the given target value from the tree while maintaining a // binary search tree. std::shared_ptr> removeValue(std::shared_ptr> subTreePtr, const ItemType target, bool& success) override; // Removes a given node from a tree while maintaining a // binary search tree. auto removeNode(std::shared_ptr> nodePtr); // Removes the leftmost node in the left subtree of the node // pointed to by nodePtr. // Sets inorderSuccessor to the value in this node. // Returns a pointer to the revised subtree. auto removeLeftmostNode(std::shared_ptr> subTreePtr, ItemType& inorderSuccessor); // Returns a pointer to the node containing the given value, // or nullptr if not found. auto findNode(std::shared_ptr> treePtr, const ItemType& target) const; public: //------------------------------------------------------------ // Constructor and Destructor Section. //------------------------------------------------------------ BinarySearchTree(); BinarySearchTree(const ItemType& rootItem); BinarySearchTree(const BinarySearchTree& tree); virtual ~BinarySearchTree(); //------------------------------------------------------------ // Public Methods Section. //------------------------------------------------------------ bool isEmpty() const override; int getHeight() const override; int getNumberOfNodes() const override; ItemType getRootData() const throw(PrecondViolatedExcep) override; void setRootData(const ItemType& newData) const throw(PrecondViolatedExcep); bool add(const ItemType& newEntry) override; bool remove(const ItemType& anEntry) override; void clear() override; ItemType getEntry(const ItemType& anEntry) const throw(NotFoundException) override; bool contains(const ItemType& anEntry) const override; //------------------------------------------------------------ // Public Traversals Section. //------------------------------------------------------------ void preorderTraverse(void visit(ItemType&)) const override; void inorderTraverse(void visit(ItemType&)) const override; void postorderTraverse(void visit(ItemType&)) const override; //------------------------------------------------------------ // Overloaded Operator Section. //------------------------------------------------------------ BinarySearchTree& operator=(const BinarySearchTree& rightHandSide); }; // end BinarySearchTree #include "BinarySearchTree.cpp" #endif

-----------------------------------------------------------------------------------------------

BinaryTreeInterface.h is shown below

/** Listing 15-1. @file BinaryTreeInterface.h */

#ifndef BINARY_TREE_INTERFACE_ #define BINARY_TREE_INTERFACE_

#include "NotFoundException.h"

template class BinaryTreeInterface { public: /** Tests whether this binary tree is empty. @return True if the binary tree is empty, or false if not. */ virtual bool isEmpty() const = 0; /** Gets the height of this binary tree. @return The height of the binary tree. */ virtual int getHeight() const = 0; /** Gets the number of nodes in this binary tree. @return The number of nodes in the binary tree. */ virtual int getNumberOfNodes() const = 0; /** Gets the data that is in the root of this binary tree. @pre The binary tree is not empty. @post The roots data has been returned, and the binary tree is unchanged. @return The data in the root of the binary tree. */ virtual ItemType getRootData() const = 0; /** Replaces the data item in the root of this binary tree with the given data, if the tree is not empty. However, if the tree is empty, inserts a new root node containing the given data into the tree. @pre None. @post The data in the root of the binary tree is as given. @param newData The data for the root. */ virtual void setRootData(const ItemType& newData) = 0; /** Adds a new node containing the given data to this binary tree. @param newData The data for the new node. @post The binary tree contains a new node. @return True if the addition is successful, or false not. */ virtual bool add(const ItemType& newData) = 0; /** Removes the node containing the given data item from this binary tree. @param data The data value to remove from the binary tree. @return True if the removal is successful, or false not. */ virtual bool remove(const ItemType& data) = 0; /** Removes all nodes from this binary tree. */ virtual void clear() = 0; /** Gets a specific entry in this binary tree. @post The desired entry has been returned, and the binary tree is unchanged. If no such entry was found, an exception is thrown. @param anEntry The entry to locate. @return The entry in the binary tree that matches the given entry. @throw NotFoundException if the given entry is not in the tree. */ virtual ItemType getEntry(const ItemType& anEntry) const throw(NotFoundException) = 0; /** Tests whether a given entry occurs in this binary tree. @post The binary search tree is unchanged. @param anEntry The entry to find. @return True if the entry occurs in the tree, or false if not. */ virtual bool contains(const ItemType& anEntry) const = 0; /** Traverses this binary tree in preorder (inorder, postorder) and calls the function visit once for each node. @param visit A client-defined function that performs an operation on or with the data in each visited node. */ virtual void preorderTraverse(void visit(ItemType&)) const = 0; virtual void inorderTraverse(void visit(ItemType&)) const = 0; virtual void postorderTraverse(void visit(ItemType&)) const = 0; /** Destroys object and frees memory allocated by object. */ virtual ~BinaryTreeInterface() { } }; // end BinaryTreeInterface #endif