implement the class BinarySearchTree as given in listing 16-4 Program must compi
ID: 3866554 • Letter: I
Question
implement the class BinarySearchTree as given in listing 16-4
Program must compile and run.
Driver program should:
insert 21 random numbers (1-100) on the tree
remove the last number inserted
and display the tree
To display just use in order traversal
No user input for driver program.
Use the BST ADT BinarySearchTree.h
________________________________________________________________________________________________
//Â Created by Frank M. Carrano and Timothy M. Henry.
//Â Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.
/** @file BinaryNode.cpp */
#include "BinaryNode.h"
#include <cstddef>
template<class ItemType>
BinaryNode<ItemType>::BinaryNode()
: item(nullptr), leftChildPtr(nullptr), rightChildPtr(nullptr)
{ } // end default constructor
template<class ItemType>
BinaryNode<ItemType>::BinaryNode(const ItemType& anItem)
: item(anItem), leftChildPtr(nullptr), rightChildPtr(nullptr)
{ } // end constructor
template<class ItemType>
BinaryNode<ItemType>::BinaryNode(const ItemType& anItem,
std::shared_ptr<BinaryNode<ItemType>> leftPtr,
std::shared_ptr<BinaryNode<ItemType>> rightPtr)
: item(anItem), leftChildPtr(leftPtr), rightChildPtr(rightPtr)
{ } // end constructor
template<class ItemType>
void BinaryNode<ItemType>::setItem(const ItemType& anItem)
{
item = anItem;
} // end setItem
template<class ItemType>
ItemType BinaryNode<ItemType>::getItem() const
{
return item;
} // end getItem
template<class ItemType>
bool BinaryNode<ItemType>::isLeaf() const
{
return ((leftChildPtr == nullptr) && (rightChildPtr == nullptr));
}
template<class ItemType>
void BinaryNode<ItemType>::setLeftChildPtr(std::shared_ptr<BinaryNode<ItemType>> leftPtr)
{
leftChildPtr = leftPtr;
} // end setLeftChildPtr
template<class ItemType>
void BinaryNode<ItemType>::setRightChildPtr(std::shared_ptr<BinaryNode<ItemType>> rightPtr)
{
rightChildPtr = rightPtr;
} // end setRightChildPtr
template<class ItemType>
auto BinaryNode<ItemType>::getLeftChildPtr() const
{
return leftChildPtr;
} // end getLeftChildPtr
template<class ItemType>
auto BinaryNode<ItemType>::getRightChildPtr() const
{
return rightChildPtr;
} // end getRightChildPtr
___________________________________________________________________________________
//Â Created by Frank M. Carrano and Timothy M. Henry.
//Â Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.
/** @file BinaryNodeTree.cpp */
#include "BinaryNodeTree.h"
#include "BinaryNode.h"
#include <iostream>
//////////////////////////////////////////////////////////////
// Protected Utility Methods Section
//////////////////////////////////////////////////////////////
template<class ItemType>
int BinaryNodeTree<ItemType>::getHeightHelper(std::shared_ptr<BinaryNode<ItemType>> subTreePtr) const
{
if (subTreePtr == nullptr)
return 0;
else
return 1 + std::max(getHeightHelper(subTreePtr->getLeftChildPtr()),
getHeightHelper(subTreePtr->getRightChildPtr()));
} // end getHeightHelper
template<class ItemType>
int BinaryNodeTree<ItemType>::getNumberOfNodesHelper(std::shared_ptr<BinaryNode<ItemType>> subTreePtr) const
{
if (subTreePtr == nullptr)
return 0;
else
return 1 + getNumberOfNodesHelper(subTreePtr->getLeftChildPtr())
+ getNumberOfNodesHelper(subTreePtr->getRightChildPtr());
} // end getNumberOfNodesHelper
template<class ItemType>
auto BinaryNodeTree<ItemType>::balancedAdd(std::shared_ptr<BinaryNode<ItemType>> subTreePtr,
std::shared_ptr<BinaryNode<ItemType>> newNodePtr)
{
if (subTreePtr == nullptr)
return newNodePtr;
else
{
auto leftPtr = subTreePtr->getLeftChildPtr();
auto rightPtr = subTreePtr->getRightChildPtr();
if (getHeightHelper(leftPtr) > getHeightHelper(rightPtr))
{
rightPtr = balancedAdd(rightPtr , newNodePtr);
subTreePtr->setRightChildPtr(rightPtr );
}
else
{
leftPtr = balancedAdd(leftPtr, newNodePtr);
subTreePtr->setLeftChildPtr(leftPtr);
} // end if
return subTreePtr;
} // end if
} // end balancedAdd
template<class ItemType>
std::shared_ptr<BinaryNode<ItemType>> BinaryNodeTree<ItemType>::moveValuesUpTree(std::shared_ptr<BinaryNode<ItemType>> subTreePtr)
{
auto leftPtr = subTreePtr->getLeftChildPtr();
auto rightPtr = subTreePtr->getRightChildPtr();
int leftHeight = getHeightHelper(leftPtr);
int rightHeight = getHeightHelper(rightPtr);
if (leftHeight > rightHeight)
{
subTreePtr->setItem(leftPtr->getItem());
leftPtr = moveValuesUpTree(leftPtr);
subTreePtr->setLeftChildPtr(leftPtr);
return subTreePtr;
}
else
{
if (rightPtr != nullptr)
{
subTreePtr->setItem(rightPtr->getItem());
rightPtr =moveValuesUpTree(rightPtr);
subTreePtr->setRightChildPtr(rightPtr);
return subTreePtr;
}
else
{
//this was a leaf!
// value not important
return nullptr;
} // end if
} // end if
} // end moveValuesUpTree
/** Depth-first search of tree for item.
@param subTreePtr tree to search.
@param target target item to find.
@param success communicate to client we found it.
@returns A pointer to node containing the item. */
template<class ItemType>
std::shared_ptr<BinaryNode<ItemType>> BinaryNodeTree<ItemType>::removeValue(std::shared_ptr<BinaryNode<ItemType>> subTreePtr,
const ItemType target,
bool& success)
{
if(subTreePtr == nullptr) // not found here
return subTreePtr;
if (subTreePtr->getItem() == target) // found it
{
subTreePtr = moveValuesUpTree(subTreePtr);
success = true;
return subTreePtr;
}
else
{
auto targetNodePtr = removeValue(subTreePtr->getLeftChildPtr(), target, success);
subTreePtr->setLeftChildPtr(targetNodePtr);
if (!success) // no need to search right subTree
{
targetNodePtr = removeValue(subTreePtr->getRightChildPtr(), target, success);
subTreePtr->setRightChildPtr(targetNodePtr);
} // end if
return subTreePtr;
} // end if
} // end removeValue
template<class ItemType>
auto BinaryNodeTree<ItemType>::findNode(std::shared_ptr<BinaryNode<ItemType>> treePtr,
const ItemType& target,
bool& success) const
{
if (treePtr == nullptr) // not found here
return treePtr;
if (treePtr->getItem() == target) // found it
{
success = true;
return treePtr;
}
else
{
std::shared_ptr<BinaryNode<ItemType>> targetNodePtr = findNode(treePtr->getLeftChildPtr(), target, success);
if (!success) // no need to search right subTree
{
targetNodePtr = findNode(treePtr->getRightChildPtr(), target, success);
} // end if
return targetNodePtr;
} // end if
} // end findNode
template<class ItemType>
std::shared_ptr<BinaryNode<ItemType>> BinaryNodeTree<ItemType>::copyTree(const std::shared_ptr<BinaryNode<ItemType>> oldTreeRootPtr) const
{
std::shared_ptr<BinaryNode<ItemType>> newTreePtr;
// Copy tree nodes during a preorder traversal
if (oldTreeRootPtr != nullptr)
{
// Copy node
newTreePtr = std::make_shared<BinaryNode<ItemType>>(oldTreeRootPtr->getItem(), nullptr, nullptr);
newTreePtr->setLeftChildPtr(copyTree(oldTreeRootPtr->getLeftChildPtr()));
newTreePtr->setRightChildPtr(copyTree(oldTreeRootPtr->getRightChildPtr()));
} // end if
return newTreePtr;
} // end copyTree
template<class ItemType>
void BinaryNodeTree<ItemType>::destroyTree(std::shared_ptr<BinaryNode<ItemType>> subTreePtr)
{
if (subTreePtr != nullptr)
{
destroyTree(subTreePtr->getLeftChildPtr());
destroyTree(subTreePtr->getRightChildPtr());
subTreePtr.reset(); // decrement reference count to node
} // end if
} // end destroyTree
//////////////////////////////////////////////////////////////
// Protected Tree Traversal Sub-Section
//////////////////////////////////////////////////////////////
template<class ItemType>
void BinaryNodeTree<ItemType>::preorder(void visit(ItemType&), std::shared_ptr<BinaryNode<ItemType>> treePtr) const
{
if (treePtr != nullptr)
{
ItemType theItem = treePtr->getItem();
visit(theItem);
// visit(treePtr->getItem());
preorder(visit, treePtr->getLeftChildPtr());
preorder(visit, treePtr->getRightChildPtr());
} // end if
} // end preorder
template<class ItemType>
void BinaryNodeTree<ItemType>::inorder(void visit(ItemType&), std::shared_ptr<BinaryNode<ItemType>> treePtr) const
{
if (treePtr != nullptr)
{
inorder(visit, treePtr->getLeftChildPtr());
ItemType theItem = treePtr->getItem();
visit(theItem);
inorder(visit, treePtr->getRightChildPtr());
} // end if
} // end inorder
template<class ItemType>
void BinaryNodeTree<ItemType>::postorder(void visit(ItemType&), std::shared_ptr<BinaryNode<ItemType>> treePtr) const
{
if (treePtr != nullptr)
{
postorder(visit, treePtr->getLeftChildPtr());
postorder(visit, treePtr->getRightChildPtr());
ItemType theItem = treePtr->getItem();
visit(theItem);
} // end if
} // end postorder
//////////////////////////////////////////////////////////////
// PUBLIC METHODS BEGIN HERE
//////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////
// Constructor and Destructor Section
//////////////////////////////////////////////////////////////
template<class ItemType>
BinaryNodeTree<ItemType>::BinaryNodeTree()
{ } // end default constructor
template<class ItemType>
BinaryNodeTree<ItemType>::BinaryNodeTree(const ItemType& rootItem)
:rootPtr(std::make_shared<BinaryNode<ItemType>>(rootItem, nullptr, nullptr))
{ } // end constructor
template<class ItemType>
BinaryNodeTree<ItemType>::BinaryNodeTree(const ItemType& rootItem,
const std::shared_ptr<BinaryNodeTree<ItemType>> leftTreePtr,
const std::shared_ptr<BinaryNodeTree<ItemType>> rightTreePtr)
:rootPtr(std::make_shared<BinaryNode<ItemType>>(rootItem,
copyTree(leftTreePtr->rootPtr),
copyTree(rightTreePtr->rootPtr)))
{ } // end constructor
template<class ItemType>
BinaryNodeTree<ItemType>::BinaryNodeTree(const BinaryNodeTree<ItemType>& treePtr)
{
rootPtr = copyTree(treePtr.rootPtr);
} // end copy constructor
template<class ItemType>
BinaryNodeTree<ItemType>::~BinaryNodeTree()
{
destroyTree(rootPtr);
} // end destructor
//////////////////////////////////////////////////////////////
// Public BinaryTreeInterface Methods Section
//////////////////////////////////////////////////////////////
template<class ItemType>
bool BinaryNodeTree<ItemType>::isEmpty() const
{
return rootPtr == nullptr;
} // end isEmpty
template<class ItemType>
int BinaryNodeTree<ItemType>::getHeight() const
{
return getHeightHelper(rootPtr);
} // end getHeight
template<class ItemType>
int BinaryNodeTree<ItemType>::getNumberOfNodes() const
{
return getNumberOfNodesHelper(rootPtr);
} // end getNumberOfNodes
template<class ItemType>
void BinaryNodeTree<ItemType>::clear()
{
destroyTree(rootPtr);
rootPtr.reset();
} // end clear
template<class ItemType>
ItemType BinaryNodeTree<ItemType>::getRootData() const throw(PrecondViolatedExcep)
{
if (isEmpty())
throw PrecondViolatedExcep("getRootData() called with empty tree.");
return rootPtr->getItem();
} // end getRootData
template<class ItemType>
void BinaryNodeTree<ItemType>::setRootData(const ItemType& newItem)
{
if (isEmpty())
rootPtr = std::make_shared<BinaryNode<ItemType>>(newItem, nullptr, nullptr);
else
rootPtr->setItem(newItem);
} // end setRootData
template<class ItemType>
bool BinaryNodeTree<ItemType>::add(const ItemType& newData)
{
auto newNodePtr = std::make_shared<BinaryNode<ItemType>>(newData);
rootPtr = balancedAdd(rootPtr, newNodePtr);
return true;
} // end add
template<class ItemType>
bool BinaryNodeTree<ItemType>::remove(const ItemType& target)
{
bool isSuccessful = false;
rootPtr = removeValue(rootPtr, target, isSuccessful);
return isSuccessful;
} // end remove
template<class ItemType>
ItemType BinaryNodeTree<ItemType>::getEntry(const ItemType& anEntry) const throw(NotFoundException)
{
bool isSuccessful = false;
auto binaryNodePtr = findNode(rootPtr, anEntry, isSuccessful);
if (isSuccessful)
return binaryNodePtr->getItem();
else
throw NotFoundException("Entry not found in tree!");
} // end getEntry
template<class ItemType>
bool BinaryNodeTree<ItemType>:: contains(const ItemType& anEntry) const
{
bool isSuccessful = false;
findNode(rootPtr, anEntry, isSuccessful);
return isSuccessful;
} // end contains
//////////////////////////////////////////////////////////////
// Public Traversals Section
//////////////////////////////////////////////////////////////
template<class ItemType>
void BinaryNodeTree<ItemType>::preorderTraverse(void visit(ItemType&)) const
{
preorder(visit, rootPtr);
} // end preorderTraverse
template<class ItemType>
void BinaryNodeTree<ItemType>::inorderTraverse(void visit(ItemType&)) const
{
inorder(visit, rootPtr);
} // end inorderTraverse
template<class ItemType>
void BinaryNodeTree<ItemType>::postorderTraverse(void visit(ItemType&)) const
{
postorder(visit, rootPtr);
} // end postorderTraverse
//////////////////////////////////////////////////////////////
// Overloaded Operator
//////////////////////////////////////////////////////////////
template<class ItemType>
BinaryNodeTree<ItemType>& BinaryNodeTree<ItemType>::operator=(
const BinaryNodeTree<ItemType>& rightHandSide)
{
if (!isEmpty())
clear();
this = copyTree(&rightHandSide);
return *this;
} // end operator=
____________________________________________________________________________________________
//Â Created by Frank M. Carrano and Timothy M. Henry.
//Â Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.
/** ADT binary tree: Link-based implementation.
Listing 16-3.
@file BinaryNodeTree.h */
#ifndef BINARY_NODE_TREE_
#define BINARY_NODE_TREE_
#include <memory>
#include "BinaryTreeInterface.h"
#include "BinaryNode.h"
#include "PrecondViolatedExcep.h"
#include "NotFoundException.h"
template<class ItemType>
class BinaryNodeTree : public BinaryTreeInterface<ItemType>
{
private:
std::shared_ptr<BinaryNode<ItemType>> rootPtr;
protected:
//------------------------------------------------------------
// Protected Utility Methods Section:
// Recursive helper methods for the public methods.
//------------------------------------------------------------
int getHeightHelper(std::shared_ptr<BinaryNode<ItemType>> subTreePtr) const;
int getNumberOfNodesHelper(std::shared_ptr<BinaryNode<ItemType>> subTreePtr) const;
// Recursively adds a new node to the tree in a left/right fashion to
// keep the tree balanced.
auto balancedAdd(std::shared_ptr<BinaryNode<ItemType>> subTreePtr,
std::shared_ptr<BinaryNode<ItemType>> newNodePtr);
// Copies values up the tree to overwrite value in current node until
// a leaf is reached; the leaf is then removed, since its value is
// stored in the parent.
std::shared_ptr<BinaryNode<ItemType>> moveValuesUpTree(std::shared_ptr<BinaryNode<ItemType>> subTreePtr);
// Removes the target value from the tree by calling moveValuesUpTree
// to overwrite value with value from child.
virtual std::shared_ptr<BinaryNode<ItemType>>
removeValue(std::shared_ptr<BinaryNode<ItemType>> subTreePtr,
const ItemType target, bool& success);
// Recursively searches for target value in the tree by using a
// preorder traversal.
auto findNode(std::shared_ptr<BinaryNode<ItemType>> treePtr,
const ItemType& target,
bool& success) const;
// Copies the tree rooted at treePtr and returns a pointer to
// the copy.
std::shared_ptr<BinaryNode<ItemType>> copyTree(const std::shared_ptr<BinaryNode<ItemType>> oldTreeRootPtr) const;
// Recursively deletes all nodes from the tree.
void destroyTree(std::shared_ptr<BinaryNode<ItemType>> subTreePtr);
// Recursive traversal helper methods:
void preorder(void visit(ItemType&), std::shared_ptr<BinaryNode<ItemType>> treePtr) const;
void inorder(void visit(ItemType&), std::shared_ptr<BinaryNode<ItemType>> treePtr) const;
void postorder(void visit(ItemType&), std::shared_ptr<BinaryNode<ItemType>> treePtr) const;
public:
//------------------------------------------------------------
// Constructor and Destructor Section.
//------------------------------------------------------------
BinaryNodeTree();
BinaryNodeTree(const ItemType& rootItem);
BinaryNodeTree(const ItemType& rootItem,
const std::shared_ptr<BinaryNodeTree<ItemType>> leftTreePtr,
const std::shared_ptr<BinaryNodeTree<ItemType>> rightTreePtr);
BinaryNodeTree(const BinaryNodeTree<ItemType>& tree);
virtual ~BinaryNodeTree();
//------------------------------------------------------------
// Public BinaryTreeInterface Methods Section.
//------------------------------------------------------------
bool isEmpty() const;
int getHeight() const;
int getNumberOfNodes() const;
ItemType getRootData() const throw(PrecondViolatedExcep);
void setRootData(const ItemType& newData);
bool add(const ItemType& newData); // Adds a node
bool remove(const ItemType& data); // Removes a node
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.
//------------------------------------------------------------
BinaryNodeTree& operator=(const BinaryNodeTree& rightHandSide);
}; // end BinaryNodeTree
#include "BinaryNodeTree.cpp"
#endif
_____________________________________________________________
//Â Created by Frank M. Carrano and Timothy M. Henry.
//Â Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.
/** Listing 15-1.
@file BinaryTreeInterface.h */
#ifndef BINARY_TREE_INTERFACE_
#define BINARY_TREE_INTERFACE_
#include "NotFoundException.h"
template<class ItemType>
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 root’s 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
__________________________________________________________________________________
//Â Created by Frank M. Carrano and Timothy M. Henry.
//Â Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.
/** Listing 7-5.
@file PrecondViolatedExcep.h */
#ifndef NOTFOUND_EXCEP_
#define NOTFOUND_EXCEP_
#include <stdexcept>
#include <string>
class NotFoundException : public std::logic_error
{
public:
NotFoundException(const std::string& message = "")
: std::logic_error("Not Found Exception: " + message)
{
}
}; // end NotFoundException
#endif
__________________________________________________________________________________
//Â Created by Frank M. Carrano and Timothy M. Henry.
//Â Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.
/** Listing 7-5.
@file PrecondViolatedExcep.h */
#ifndef PRECOND_VIOLATED_EXCEP_
#define PRECOND_VIOLATED_EXCEP_
#include <stdexcept>
#include <string>
class PrecondViolatedExcep : public std::logic_error
{
public:
PrecondViolatedExcep(const std::string& message = "")
: std::logic_error("Precondition Violated Exception: " + message)
{
}
}; // end PrecondViolatedExcep
#endif
_______________________________________________________________________________
//Â Created by Frank M. Carrano and Timothy M. Henry.
//Â Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.
/** A class of nodes for an array-based binary tree.
Listing 16-1.
@file TreeNode.h */
#ifndef TREE_NODE_
#define TREE_NODE_
template<class ItemType>
class TreeNode
{
private:
ItemType item; // Data portion
int leftChild; // Index to left child
int rightChild; // Index to right child
public:
TreeNode();
TreeNode(const ItemType& nodeItem, int left, int right);
// Declarations of the methods setItem, getItem, setLeft, getLeft,
// setRight, and getRight are here.
void setItem(const ItemType& anItem);
ItemType getItem() const;
void setLeft(TreeNode<ItemType> leftChild);
TreeNode<ItemType> getLeft() const;
void setRight(TreeNode<ItemType> rightChild);
TreeNode<ItemType> getRight() const;
}; // end TreeNode
#include "TreeNode.cpp"
#endif
Explanation / Answer
#ifndef BST_H
#define BST_H
template <typename T>
class treeNode {
public:
treeNode *left;
treeNode *right;
T key;
treeNode(T key)
: key(key)
, left(nullptr)
, right(nullptr) {
}
};
template <typename T>
class BST {
public:
BST() {
root = nullptr;
nodes = 0;
}
BST(BST const& rhs)
: nodes(rhs.size()) {
// not yet implemented
}
BST& operator = (BST rhs) {
this->swap(rhs);
}
BST& operator = (BST&& rhs) {
this->swap(rhs);
}
~BST() {
clear(root);
}
void swap(BST& other) {
std::swap(root, other.root);
std::swap(nodes, other.nodes);
}
void clear(treeNode<T>* node) {
if(node) {
if(node->left) clear(node->left);
if(node->right) clear(node->right);
delete node;
}
}
bool isEmpty() const {
return root == nullptr;
}
void inorder(treeNode<T>*);
void traverseInorder();
void preorder(treeNode<T>*);
void traversePreorder();
void postorder(treeNode<T>*);
void traversePostorder();
void insert(T const& );
void remove(T const& );
treeNode<T>* search(const T &);
treeNode<T>* minHelper(treeNode<T>*);
treeNode<T>* min();
treeNode<T>* maxHelper(treeNode<T>*);
treeNode<T>* max();
size_t size() const;
void sort();
treeNode<T>* inOrderSuccessor(treeNode<T>*);
bool isBST(treeNode<T>*) const;
bool isBST() const;
private:
treeNode<T> *root;
size_t nodes;
};
// Smaller elements go left
// larger elements go right
template <class T>
void BST<T>::insert(T const& value) {
treeNode<T> *newNode = new treeNode<T>(value);
treeNode<T> *parent = nullptr;
// is this a new tree?
if(isEmpty()) {
root = newNode;
++nodes;
return;
}
//Note: ALL insertions are as leaf nodes
treeNode<T>* curr = root;
// Find the Node's parent
while(curr) {
parent = curr;
curr = newNode->key > curr->key ? curr->right : curr->left;
}
if(newNode->key < parent->key)
parent->left = newNode;
else
parent->right = newNode;
++nodes;
}
template <typename T>
void BST<T>::remove(T const& data) {
if(isEmpty()) {
throw std::runtime_error("Invalid Action!");
}
treeNode<T> *curr = root;
treeNode<T> *parent;
// root to leaf search (top-down)
while(curr) {
if(curr->key == data) {
break;
} else {
parent = curr;
curr = data > curr->key ? curr->right : curr->left;
}
}
if(curr == nullptr) {
cout << "key not found! " << endl;
return;
}
// 3 cases :
// 1. We're removing a leaf node
// 2. We're removing a node with a single child
// 3. we're removing a node with 2 children
//We're looking at a leaf node
if( curr->left == nullptr and curr->right == nullptr) {
if(parent->left == curr)
parent->left = nullptr;
else
parent->right = nullptr;
delete curr;
--nodes;
return;
}
// Node with single child
if((curr->left == nullptr and curr->right != nullptr) or (curr->left != nullptr and curr->right == nullptr)) {
if(curr->left == nullptr and curr->right != nullptr) {
if(parent->left == curr) {
parent->left = curr->right;
} else {
parent->right = curr->right;
}
} else { // left child present, no right child
if(parent->left == curr) {
parent->left = curr->left;
} else {
parent->right = curr->left;
}
}
delete curr;
--nodes;
return;
}
// Node with 2 children
// replace node with smallest value in right subtree
if (curr->left != nullptr and curr->right != nullptr) {
treeNode<T> *curr_right = curr->right;
if(curr_right->left == nullptr and curr_right->right == nullptr) {
curr->key = curr_right->key;
delete curr_right;
curr->right = nullptr;
} else { // right child has children
//if the node's right child has a left child
// Move all the way down left to locate smallest element
if((curr->right)->left != nullptr) {
treeNode<T>* lcurr;
treeNode<T>* lcurr_parent;
lcurr_parent = curr->right;
lcurr = (curr->right)->left;
while(lcurr->left != nullptr) {
lcurr_parent = lcurr;
lcurr = lcurr->left;
}
curr->key = lcurr->key;
delete lcurr;
lcurr_parent->left = nullptr;
} else { // (curr->right)->right != nullptr
treeNode<T> *tmp = curr->right;
curr->key = tmp->key;
curr->right = tmp->right;
delete tmp;
}
}
--nodes;
}
}
template <typename T>
treeNode<T>* BST<T> :: search(T const& value) {
treeNode<T> *curr = root;
while (curr) {
if(curr->key == value) {
return curr;
} else if(value < curr->key) {
curr = curr->left;
} else curr = curr->right;
}
return nullptr;
}
template <typename T>
treeNode<T>* BST <T> :: minHelper(treeNode<T>* node) {
if(node->left == nullptr)
return node;
minHelper(node->left);
}
template <typename T>
treeNode<T>* BST <T> :: min() {
return minHelper(root);
}
template <typename T>
treeNode<T>* BST <T> :: maxHelper(treeNode<T>* node) {
if(node->right == nullptr)
return node;
maxHelper(node->right);
}
template <typename T>
treeNode<T>* BST <T> :: max() {
return maxHelper(root);
}
template<typename T>
size_t BST<T>::size() const {
return nodes;
}
template<typename T>
void BST<T>::inorder(treeNode<T>* node) {
if(node != nullptr) {
if(node->left) inorder(node->left);
cout << " " << node->key << " ";
if(node->right)
inorder(node->right);
}
}
template<typename T>
void BST<T>::traverseInorder() {
inorder(root);
}
template<typename T>
void BST<T>::sort() {
inorder(root);
}
template<typename T>
void BST<T>::preorder(treeNode<T>* node) {
if(node != nullptr) {
cout << " " << node->key << " ";
if(node->left) preorder(node->left);
if(node->right) preorder(node->right);
}
}
template<typename T>
void BST<T>::traversePreorder() {
preorder(root);
}
template<typename T>
void BST<T>::postorder(treeNode<T>* node) {
if(node != nullptr) {
if(node->left) postorder(node->left);
if(node->right) postorder(node->right);
cout << " " << node->key << " ";
}
}
template<typename T>
void BST<T>::traversePostorder() {
postorder(root);
}
template <class T>
treeNode<T>* BST<T> :: inOrderSuccessor(treeNode<T>* node) {
if(node->right != nullptr)
return minHelper(node->right);
treeNode<T>* succ = nullptr;
treeNode<T>* curr = root;
// Start from root and search for successor down the tree
while (curr != nullptr) {
if (node->key < curr->key) {
succ = curr;
curr = curr->left;
} else if (node->key > curr->key)
curr = curr->right;
else
break;
}
return succ;
}
template<typename T>
bool BST<T>::isBST(treeNode<T>* node) const {
static struct treeNode<T> *prev = nullptr;
// traverse the tree in inorder fashion and keep track of prev node
if (node) {
if (!isBST(node->left))
return false;
// Allows only distinct valued nodes
if (prev != nullptr and node->key <= prev->key)
return false;
prev = node;
return isBST(node->right);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.