Implement the class BinarySearchTree, as given in listing 16-4 (below) 1. Random
ID: 3776437 • Letter: I
Question
Implement the class BinarySearchTree, as given in listing 16-4 (below)
1. Randomly generate 100 unique values in the range of [1-200] and insert them into a binary search tree (BST1). Print height and inorder output of the BST1 tree.
2. Randomly generate 10 unique values in the range of [1-200] where there is an overlap with the previous values and insert them into another binary search tree (BST2). Print preorder, inorder, and postorder output of the BST2 tree.
3. Find and remove any values of BST2 from BST1. Print height, number of nodes, and inorder output of the modified BST1 tree.
4. Clear the binary search trees. Print whether trees are empty before and after clear operation.
// Listing 16-4.
/** Link-based implementation of the ADT binary search tree.
@file BinarySearchTree.h */
#ifndef BINARY_SEARCH_TREE_
#define BINARY_SEARCH_TREE_
#include "BinaryTreeInterface.h"
#include "BinaryNode.h"
#include "BinaryNodeTree.h"
#include "NotFoundException.h"
#include "PrecondViolatedExcept.h"
#include <memory>
template<class ItemType>
class BinarySearchTree : public BinaryNodeTree<ItemType>
{
private:
std::shared_ptr<BinaryNode<ItemType>> rootPtr;
protected:
//------------------------------------------------------------
// Protected Utility Methods Section:
// Recursive helper methods for the public methods.
//------------------------------------------------------------
// Places a given new node at its proper position in this binary
// search tree.
auto placeNode(std::shared_ptr<BinaryNode<ItemType>> subTreePtr,
std::shared_ptr<BinaryNode<ItemType>> newNode);
// Removes the given target value from the tree while maintaining a
// binary search tree.
auto removeValue(std::shared_ptr<BinaryNode<ItemType>> subTreePtr,
const ItemType target,
bool& isSuccessful) override;
// Removes a given node from a tree while maintaining a binary search tree.
auto removeNode(std::shared_ptr<BinaryNode<ItemType>> 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<BinaryNode<ItemType>>subTreePtr,
ItemType& inorderSuccessor);
// Returns a pointer to the node containing the given value,
// or nullptr if not found.
auto findNode(std::shared_ptr<BinaryNode<ItemType>> treePtr,
const ItemType& target) const;
public:
//------------------------------------------------------------
// Constructor and Destructor Section.
//------------------------------------------------------------
BinarySearchTree();
BinarySearchTree(const ItemType& rootItem);
BinarySearchTree(const BinarySearchTree<ItemType>& tree);
virtual ~BinarySearchTree();
//------------------------------------------------------------
// Public Methods Section.
//------------------------------------------------------------
bool isEmpty() const;
int getHeight() const;
int getNumberOfNodes() const;
ItemType getRootData() const throw(PrecondViolatedExcept);
void setRootData(const ItemType& newData);
bool add(const ItemType& newEntry);
bool remove(const ItemType& target);
void clear();
ItemType getEntry(const ItemType& anEntry) const throw(NotFoundException);
bool contains(const ItemType& anEntry) const;
//------------------------------------------------------------
// Public Traversals Section.
//------------------------------------------------------------
void preorderTraverse(void visit(ItemType&)) const;
void inorderTraverse(void visit(ItemType&)) const;
void postorderTraverse(void visit(ItemType&)) const;
//------------------------------------------------------------
// Overloaded Operator Section.
//------------------------------------------------------------
BinarySearchTree<ItemType>&
operator=(const BinarySearchTree<ItemType>& rightHandSide);
}; // end BinarySearchTree
#include "BinarySearchTree.cpp"
#endif
Explanation / Answer
auto placeNode(std::shared_ptr<BinaryNode<ItemType>> subTreePtr, std::shared_ptr<BinaryNode<ItemType>> newNode);
{
if (subTreePtr->data < newNode->data)
{
placeNode(subTreePtr->right, newNode);
}
else
{
placeNode(subtree->left, newNode);
}
}
auto findNode(std::shared_ptr<BinaryNode<ItemType>> treePtr,
const ItemType& target) const
{
if (treePtr == target)
return treePtr;
else if (target->data < treePtr->data)
return findNode(treePtr->left, target);
else
return findNode(treePtr->right, target);
}
bool isEmpty()
{
if rootPtr == NULL)
return true;
else
return false;
}
int findHeight(std::shared_ptr<BinaryNode<ItemType>> treePtr)
{
if (treePtr == NULL)
return 0;
int l = findHeight(treePtr->left);
int r = findHeight(treePtr->right);
return max (l, r) + 1;
}
int getHeight()
{
return findHeight(rootPtr);
}
void visit(ItemType &root)
{
if (root == NULL) return;
cout<<root->data<<" ";
}
void preorderTraverse(void visit(ItemType& ptr)) const
{
if (ptr == NULL)
return;
visit(ptr);
preorderTraverse(visit(ptr->left));
preorderTraverse(visit(ptr->right));
}
void inorderTraverse(void visit(ItemType& ptr)) const
{
if (ptr == NULL)
return;
inorderTraverse(visit(ptr->left));
visit(ptr);
inorderTraverse(visit(ptr->right));
}
void postTraverse(void visit(ItemType& ptr)) const
{
if (ptr == NULL)
return;
postTraverse(visit(tree->left));
postTraverse(visit(tree->right));
visit(tree);
}