Working With Binary Search Trees Complete the following exercises using the cs20
ID: 3837100 • Letter: W
Question
Working With Binary Search Trees
Complete the following exercises using the cs20::BST class presented in class.
1. Without using a TreeIterator, create a new method called total that takes an no arguments and determines that the sum of all the elements stored in the BinarySearchTree. If the root of the tree is nullptr, then your method should throw an InvalidTreeArgument exception. The prototype of this method should be:
Because the method has been marked const, your implementation will not be able to change any of the data members found in the BinarySearchTree. Instead, you should use recursion to walk all the nodes in the tree and return the total seen so far in the recursive stack.
For example, for the BST shown below:
total( ) should return 338 (= 32 + 24 + 41 + 21 + 28 + 36 + 47 + 14 + 25 + 31 + 39)
Create a test driver that exercises this new feature, prints the tree and the results of this new operation.
2. Without using a TreeIterator, create a new method called isMatchingTree that takes an BST parameter and determines if this tree has the exact same matching structure as the passed parameter. In other words, the exact same data values need to be found in both trees in the exact same structural arrangement. If the root of the tree is nullptr, your method should throw an InvalidTreeArgument exception. The prototype for this method should be:
Because the method has been marked const, your implementation will not be able to change any of the data members found in the BinarySearchTree. Instead, you should use recursion to walk all the nodes in the tree and verify that the same matching element value is found in each node.
Create a test driver that exercises this new feature, prints the tree and the results of this new operation.
Here is the code with classes
//////////////////////////////////////////////////////////////////////////////////////////BST.cpp//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#ifndef BST_CPP
#define BST_CPP
#include "BST.h"
namespace cs20 {
template <class Object>
BST<Object>::BST() {
root = nullptr;
}
template <class Object>
BST<Object>::BST( const BST<Object>& rhs ) {
root = nullptr;
*this = rhs;
}
template <class Object>
BST<Object>::BST( const Object& rootElement ) {
root = new BSTNode<Object>( rootElement );
}
template <class Object>
BST<Object>::~BST() {
makeEmpty();
}
template <class Object>
bool BST<Object>::isEmpty() const {
return( root == nullptr );
}
template <class Object>
void BST<Object>::makeEmpty() {
makeEmpty( root );
}
template <class Object>
void BST<Object>::makeEmpty( NodePtr & node ) {
if (node != nullptr) {
NodePtr l = node->getLeftSide();
NodePtr r = node->getRightSide();
makeEmpty( l );
makeEmpty( r );
delete node;
node = nullptr;
}
}
template <class Object>
int BST<Object>::size() const {
return( BSTNode<Object>::size( root ) );
}
template <class Object>
int BST<Object>::height() const {
return( BSTNode<Object>::height( root ) );
}
template <class Object>
const Object& BST<Object>::findMin() const throw(InvalidTreeArgument) {
if (root == nullptr)
throw InvalidTreeArgument();
return( findMin( root ) );
}
template <class Object>
const Object& BST<Object>::findMax() const throw(InvalidTreeArgument) {
if (root == nullptr)
throw InvalidTreeArgument();
return( findMax( root ) );
}
template <class Object>
const Object& BST<Object>::findMin( NodePtr node ) const {
while( node->getLeftSide() != nullptr ) {
node = node->getLeftSide();
}
return( node->getElement() );
}
template <class Object>
const Object& BST<Object>::findMax( NodePtr node ) const {
while( node->getRightSide() != nullptr ) {
node = node->getRightSide();
}
return( node->getElement() );
}
template <class Object>
const Object& BST<Object>::find( const Object& x ) const throw (InvalidTreeArgument) {
return( find( x, root ) );
}
template <class Object>
const Object& BST<Object>::find( const Object& x, NodePtr node ) const throw (InvalidTreeArgument) {
if (node == nullptr)
throw InvalidTreeArgument();
if (node->getElement() < x) {
return( find( x, node->getLeftSide() ) );
}
if (node->getElement() > x) {
return( find( x, node->getRightSide() ) );
}
return( node->getElement() );
}
template <class Object>
void BST<Object>::insert( const Object& x ) throw (InvalidTreeArgument) {
insert( x, root );
}
template <class Object>
void BST<Object>::insert( const Object& x, NodePtr& node ) throw (InvalidTreeArgument) {
if (node == nullptr) {
node = new BSTNode<Object>( x, nullptr, nullptr );
}
else if (x < node->element) {
insert( x, node->leftSide );
}
else if (x > node->element) {
insert( x, node->rightSide );
}
else
throw InvalidTreeArgument();
}
template <class Object>
void BST<Object>::removeMin() throw (InvalidTreeArgument) {
removeMin( root );
}
template <class Object>
void BST<Object>::removeMin( NodePtr& node ) throw (InvalidTreeArgument) {
if (node == nullptr) {
throw InvalidTreeArgument();
}
else if (node->leftSide != nullptr) {
removeMin( node->leftSide );
}
else {
NodePtr temp = node;
node = node->rightSide;
delete temp;
}
}
template <class Object>
void BST<Object>::remove( const Object& x ) throw (InvalidTreeArgument) {
remove( x, root );
}
template <class Object>
void BST<Object>::remove( const Object& x, NodePtr & node ) throw (InvalidTreeArgument) {
if (node == nullptr)
throw InvalidTreeArgument();
else if (x < node->element)
remove( x, node->leftSide );
else if (x > node->element)
remove( x, node->rightSide );
// on the matching node
else if (node->leftSide != nullptr && node->rightSide != nullptr) {
// 2 children
node->element = findMin( node->rightSide );
removeMin( node->rightSide );
}
else {
// one or no children
NodePtr temp = node;
if (node->leftSide != nullptr) {
node = node->leftSide;
}
else {
node = node->rightSide;
}
delete temp;
}
}
// Deep copy of tree
template <class Object>
const BST<Object>& BST<Object>::operator =( const BST<Object>& rhs ) {
if (this != &rhs) {
makeEmpty();
if (rhs.root != nullptr)
root = rhs.root->duplicate();
}
return( *this );
}
template <class Object>
std::ostream& BST<Object>::printBST( std::ostream& outs ) const {
if (isEmpty())
outs << "Empty BST";
else
root->printBSTNode( outs );
outs << std::endl;
return( outs );
}
template <class Object>
BSTNode<Object>* BST<Object>::getRoot() const {
return( root );
}
}
#endif
//////////////////////////////////////////LevelOrderIterator .cpp//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#ifndef LEVELORDERITERATOR_CPP
#define LEVELORDERITERATOR_CPP
#include <iostream>
#include <cstddef>
#include "BSTIterator.h"
#include "LevelOrderIterator.h"
#include "Queue.h"
namespace cs20 {
template <class Object>
LevelOrderIterator<Object>::LevelOrderIterator( const BST<Object> & theTree ) : BSTIterator<Object>( theTree ) {
q.enqueue( this->root );
}
template <class Object>
LevelOrderIterator<Object>::~LevelOrderIterator() {
}
template <class Object>
void LevelOrderIterator<Object>::first( ) {
q.makeEmpty();
if (this->root != nullptr) {
q.enqueue( this->root );
advance();
}
}
template <class Object>
void LevelOrderIterator<Object>::advance( ) {
if (q.isEmpty()) {
if (this->current == nullptr)
throw BadIterator();
this->current = nullptr;
}
else {
this->current = q.dequeue();
if (this->current->getLeftSide() != nullptr)
q.enqueue( this->current->getLeftSide() );
if (this->current->getRightSide() != nullptr)
q.enqueue( this->current->getRightSide() );
}
}
}
#endif
//////////////////////////////////////////QueueNode .cpp//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#ifndef QUEUENODE_CPP
#define QUEUENODE_CPP
#include "QueueNode.h"
namespace cs20 {
template <class Object>
QueueNode<Object>::QueueNode( const Object& theElement,
QueueNode<Object> * node ) {
element = theElement;
next = node;
}
template <class Object>
const Object& QueueNode<Object>::getElement() const {
return( element );
}
template <class Object>
QueueNode<Object>* QueueNode<Object>::getNext() const {
return( next );
}
template <class Object>
void QueueNode<Object>::setNext( QueueNode<Object> * node ) {
next = node;
}
}
#endif
//////////////////////////////////////////BSTNode .cpp//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#ifndef BSTNODE_CPP
#define BSTNODE_CPP
#include "BSTNode.h"
namespace cs20 {
template <class Object>
BSTNode<Object>::BSTNode( const Object& theElement,
BSTNode<Object> * theLeftSide,
BSTNode<Object> * theRightSide,
int theSize) {
element = theElement;
rightSide = theRightSide;
leftSide = theLeftSide;
sz = theSize;
}
template <class Object>
int BSTNode<Object>::size( BSTNode<Object> * node ) {
if (node == nullptr )
return( 0 );
else
return( 1 + size( node->rightSide ) + size( node->leftSide ) );
}
template <class Object>
int BSTNode<Object>::height( BSTNode<Object> * node ) {
if (node == nullptr )
return( -1 );
else
return( 1 + max( height( node->leftSide ), height( node->rightSide ) ) );
}
template <class Object>
BSTNode<Object> * BSTNode<Object>::duplicate( ) const {
BSTNode<Object> * newNode = new BSTNode<Object>( element );
if (rightSide != nullptr) {
newNode->rightSide = rightSide->duplicate();
}
if (leftSide != nullptr) {
newNode->leftSide = leftSide->duplicate();
}
newNode->sz = sz;
return( newNode );
}
template <class Object>
std::ostream& BSTNode<Object>::printBSTNode( std::ostream& outs ) const {
Object o = element;
outs << o << " ";
if (leftSide != nullptr)
leftSide->printBSTNode( outs );
else
outs << "LSNULLPTR ";
if (rightSide != nullptr)
rightSide->printBSTNode( outs );
else
outs << "RSNULLPTR ";
outs << std::endl;
return( outs );
}
template <class Object>
int BSTNode<Object>::max( int a, int b ) {
int result = a;
if (b > a)
result = b;
return( result );
}
template <class Object>
const Object& BSTNode<Object>::getElement() const {
return( element );
}
template <class Object>
BSTNode<Object>* BSTNode<Object>::getLeftSide() const {
return( leftSide );
}
template <class Object>
BSTNode<Object>* BSTNode<Object>::getRightSide() const {
return( rightSide );
}
}
#endif
//////////////////////////////////////////BSTMenu .cpp//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Menu.cpp : Defines the entry point for the console application.
//
#include <iostream>
#include "BadIterator.h"
#include "InvalidTreeArgument.h"
#include "LevelOrderIterator.h"
#include "LevelOrderIterator.cpp"
#include "Queue.h"
#include "Queue.cpp"
#include "QueueNode.h"
#include "QueueNode.cpp"
#include "BST.h"
#include "BST.cpp"
#include "BSTIterator.h"
#include "BSTIterator.cpp"
#include "BSTNode.h"
#include "BSTNode.cpp"
using namespace std;
using namespace cs20;
enum CHOICE {MAKEEMPTY, ISEMPTY, SIZE, HEIGHT, QUIT, PRINT, PRINTNODE, LEVELORDER, INSERT, REMOVE, SETROOT, REMOVEMIN, FINDMIN, FINDMAX, FIND };
CHOICE menu();
void printTree( const BST<int>& t );
int main(int argc, char* argv[]) {
int value;
BST<int> tree;
BSTNode<int> * node = nullptr;
CHOICE choice;
do {
choice = menu();
switch( choice ) {
case MAKEEMPTY:
tree.makeEmpty();
node = nullptr;
break;
case ISEMPTY:
if (tree.isEmpty()) {
cout << "tree is empty" << endl;
}
else {
cout << "tree is not empty" << endl;
}
break;
case SIZE:
if (node == nullptr) {
cout << "You silly... the current node is NULL!" << endl;
}
else {
cout << "size of current node=" << BSTNode<int>::size( node ) << endl;
}
break;
case HEIGHT:
if (node == nullptr) {
cout << "You silly... the current node is NULL!" << endl;
}
else {
cout << "height of current node=" << BSTNode<int>::height( node ) << endl;
}
break;
case PRINT:
printTree( tree );
break;
case PRINTNODE:
if (node == nullptr) {
cout << "You silly... the current node is NULL!" << endl;
}
else {
value = node->getElement();
cout << "value of current node=" << value << endl;
}
break;
case INSERT:
try {
cout << "Enter a value to insert: ";
cin >> value;
tree.insert( value );
} catch( InvalidTreeArgument ita ) {
cout << "InvalidTreeArgument caught!" << endl;
}
break;
case REMOVE:
try {
cout << "Enter a value to remove: ";
cin >> value;
tree.remove( value );
} catch( InvalidTreeArgument ita ) {
cout << "InvalidTreeArgument caught!" << endl;
}
break;
case SETROOT:
cout << "Enter root value: ";
cin >> value;
// not sure this is too clever...
tree = BST<int>( value );
node = tree.getRoot();
break;
case LEVELORDER:
try {
LevelOrderIterator<int> iter( tree );
iter.first();
while( iter.isValid() ) {
value = iter.retrieve();
cout << value << " ";
iter.advance();
}
cout << endl;
}
catch( BadIterator bi ) {
cout << "badIterator exception caught!" << endl;
}
break;
case FIND:
try {
cout << "Enter a value to find: ";
cin >> value;
tree.find( value );
cout << value << " was found somewhere..." << endl;
} catch( InvalidTreeArgument ita ) {
cout << "You silly... that wasn't found in the tree!" << endl;
}
break;
case FINDMIN:
try {
value = tree.findMin();
cout << value << " is the minimum data element in the tree" << endl;
} catch( InvalidTreeArgument ita ) {
cout << "InvalidTreeArgument caught!" << endl;
}
break;
case FINDMAX:
try {
value = tree.findMax();
cout << value << " is the maximum data element in the tree" << endl;
} catch( InvalidTreeArgument ita ) {
cout << "InvalidTreeArgument caught!" << endl;
}
break;
case REMOVEMIN:
try {
tree.removeMin();
} catch( InvalidTreeArgument ita ) {
cout << "InvalidTreeArgument caught!" << endl;
}
break;
case QUIT:
break;
}
} while (choice != QUIT);
return( 0 );
}
void printTree( const BST<int> & t ) {
t.printBST( cout );
}
CHOICE menu() {
char choice;
CHOICE result;
cout << "(M)akeEmpty I(s)Empty si(Z)e (H)eight setRoo(T) (P)rint printN(O)de le(V)elOrder (I)nsert (R)emove RemoveMin(Y) FindMi(N) FindMa(X) (F)ind (Q)uit: " << endl;
cin >> choice;
switch( choice ) {
case 'M':
case 'm':
result = MAKEEMPTY;
break;
case 'S':
case 's':
result = ISEMPTY;
break;
case 'Z':
case 'z':
result = SIZE;
break;
case 'H':
case 'h':
result = HEIGHT;
break;
case 'Q':
case 'q':
result = QUIT;
break;
case 'P':
case 'p':
result = PRINT;
break;
case 'O':
case 'o':
result = PRINTNODE;
break;
case 'T':
case 't':
result = SETROOT;
break;
case 'V':
case 'v':
result = LEVELORDER;
break;
case 'I':
case 'i':
result = INSERT;
break;
case 'R':
case 'r':
result = REMOVE;
break;
case 'Y':
case 'y':
result = REMOVEMIN;
break;
case 'N':
case 'n':
result = FINDMIN;
break;
case 'X':
case 'x':
result = FINDMAX;
break;
case 'F':
case 'f':
result = FIND;
break;
}
return( result );
}
//////////////////////////////////////////BST .h//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#ifndef BST_H
#define BST_H
// pragma for Visual Studio's lack of support for checked exceptions
#pragma warning( disable: 4290)
#include <iostream>
#include <cstddef>
#include "BSTNode.h"
#include "InvalidTreeArgument.h"
namespace cs20 {
template <class Object>
class BSTIterator;
template <class Object>
class BST {
public:
BST();
BST( const Object& rootElement );
BST( const BST& rhs );
~BST();
bool isEmpty() const;
void makeEmpty();
int size() const;
int height() const;
const Object& find( const Object& x ) const throw (InvalidTreeArgument);
const Object& findMin() const throw (InvalidTreeArgument);
const Object& findMax() const throw (InvalidTreeArgument);
void insert( const Object& x ) throw (InvalidTreeArgument);
void remove( const Object& x ) throw (InvalidTreeArgument);
void removeMin() throw (InvalidTreeArgument);
const BST& operator =( const BST& rhs );
std::ostream& printBST( std::ostream& outs ) const;
BSTNode<Object>* getRoot() const;
private:
typedef BSTNode<Object>* NodePtr;
NodePtr root;
void makeEmpty( NodePtr &t );
friend class BSTIterator<Object>;
const Object& find( const Object& x, NodePtr node ) const throw (InvalidTreeArgument);
const Object& findMin( NodePtr node ) const;
const Object& findMax( NodePtr node ) const;
void insert( const Object& x, NodePtr & node ) throw (InvalidTreeArgument);
void remove( const Object& x, NodePtr & node ) throw (InvalidTreeArgument);
void removeMin( NodePtr & node ) throw (InvalidTreeArgument);
};
}
#endif
//////////////////////////////////////////BSTNode .h//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#ifndef BSTNODE_H
#define BSTNODE_H
#include <iostream>
namespace cs20 {
template <class Object>
class BST;
template <class Object>
class BSTNode {
public:
BSTNode( const Object& theElement = Object(),
BSTNode * theLeftSide = nullptr,
BSTNode * theRightSide = nullptr,
int theSize = 1);
BSTNode * duplicate() const;
static int size( BSTNode * t );
static int height( BSTNode * t );
// no references to a BSTNode are returned
// publicly by either BST or BSTIterators
// these methods are only called by BST and
// BSTIterators
const Object& getElement() const;
BSTNode* getLeftSide() const;
BSTNode* getRightSide() const;
std::ostream& printBSTNode ( std::ostream& outs ) const;
friend class BST<Object>;
private:
Object element;
BSTNode* rightSide;
BSTNode* leftSide;
int sz;
static int max( int a, int b );
};
}
#endif
//////////////////////////////////////////Queue .cpp//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#ifndef QUEUE_CPP
#define QUEUE_CPP
#include "Queue.h"
namespace cs20 {
template <class Object>
Queue<Object>::Queue() {
frontNode = nullptr;
backNode = nullptr;
}
template <class Object>
Queue<Object>::Queue( const Queue<Object>& rhs ) {
frontNode = nullptr;
backNode = nullptr;
*this = rhs;
}
template <class Object>
Queue<Object>::~Queue() {
makeEmpty();
// when empty, frontNode and backNode will already be null
}
template <class Object>
bool Queue<Object>::isEmpty() const {
return( (frontNode == nullptr) );
}
template <class Object>
void Queue<Object>::makeEmpty() {
while (!isEmpty()) {
dequeue();
}
}
template <class Object>
void Queue<Object>::enqueue( const Object& data ) {
QueueNode<Object>* newNode = new QueueNode<Object>( data );
if (isEmpty()) {
frontNode = newNode;
backNode = newNode;
}
else {
backNode->setNext( newNode );
backNode = backNode->getNext();
}
}
template <class Object>
const Object Queue<Object>::dequeue() {
Object frontData = getFront();
QueueNode<Object> * oldFront = frontNode;
frontNode = frontNode->getNext();
delete oldFront;
return( frontData );
}
template <class Object>
const Object& Queue<Object>::getFront() const {
if (isEmpty()) {
throw EmptyQueue();
}
return( frontNode->getElement() );
}
// Deep copy of linked Queue
template <class Object>
const Queue<Object>& Queue<Object>::operator =( const Queue<Object>& rhs ) {
if (this != &rhs) {
makeEmpty();
QueueNode<Object> * rhsFrontNode = rhs.frontNode;
while( rhsFrontNode != nullptr) {
enqueue( rhsFrontNode->getElement() );
rhsFrontNode = rhsFrontNode->getNext();
}
}
return( *this );
}
template <class Object>
std::ostream& Queue<Object>::printQueue( std::ostream& outs ) {
if (isEmpty()) {
outs << "Empty Queue";
}
else {
QueueNode<Object> * node = frontNode;
while( node != nullptr) {
outs << node->getElement();
outs << " ";
node = node->getNext();
}
}
return( outs );
}
}
#endif
//////////////////////////////////////////Queue.h//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#ifndef QUEUE_H
#define QUEUE_H
#include <iostream>
#include "QueueNode.h"
#include "EmptyQueue.h"
namespace cs20 {
template <class Object>
class Queue {
public:
Queue();
Queue( const Queue& rhs );
~Queue();
bool isEmpty() const;
void makeEmpty();
void enqueue( const Object& data );
const Object dequeue();
const Object& getFront() const;
const Queue& operator =( const Queue& rhs );
std::ostream& printQueue( std::ostream& outs );
private:
QueueNode<Object> * frontNode;
QueueNode<Object> * backNode;
};
}
#endif
//////////////////////////////////////////BadIterator .h//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#ifndef BADITERATOR_H
#define BADITERATOR_H
#include <iostream>
#include <string>
#include <stdexcept>
namespace cs20 {
class BadIterator : public std::logic_error {
public:
BadIterator( const std::string& msg = "" );
};
}
#endif
//////////////////////////////////////////InvalidTreeArgument .h//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#ifndef INVALIDTREEARGUMENT_H
#define INVALIDTREEARGUMENT_H
#include <iostream>
#include <string>
#include <stdexcept>
namespace cs20 {
class InvalidTreeArgument : public std::logic_error {
public:
InvalidTreeArgument( const std::string& msg = "" );
};
}
#endif
//////////////////////////////////////////BSTIterator .cpp //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#ifndef BSTITERATOR_CPP
#define BSTITERATOR_CPP
#include "BSTIterator.h"
namespace cs20 {
template <class Object>
BSTIterator<Object>::BSTIterator( const BST<Object> & theTree ) : root( theTree.root ) , current( nullptr ) {
// all assignments performed above
}
template <class Object>
BSTIterator<Object>::~BSTIterator() {
}
template <class Object>
bool BSTIterator<Object>::isValid( ) const {
return( (current != nullptr) );
}
template <class Object>
const Object& BSTIterator<Object>::retrieve( ) const {
if (!(isValid())) throw BadIterator();
return( current->getElement() );
}
}
#endif
//////////////////////////////////////////BSTIterator .h//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#ifndef BSTITERATOR_H
#define BSTITERATOR_H
#include <iostream>
#include "BSTNode.h"
#include "BST.h"
#include "BadIterator.h"
namespace cs20 {
template <class Object>
class BSTIterator {
public:
BSTIterator( const BST<Object>& theTree );
virtual ~BSTIterator();
bool isValid() const;
virtual void advance() = 0;
virtual void first() = 0;
const Object& retrieve() const;
protected:
const BSTNode<Object> * current;
const BSTNode<Object> * root;
};
}
#endif
//////////////////////////////////////////LevelOrderIterator .h//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#ifndef LEVELORDERITERATOR_H
#define LEVELORDERITERATOR_H
#include <iostream>
#include "BST.h"
#include "BSTIterator.h"
#include "Queue.h"
namespace cs20 {
template <class Object>
class LevelOrderIterator : public BSTIterator<Object> {
public:
LevelOrderIterator( const BST<Object>& theTree );
virtual ~LevelOrderIterator();
void advance();
void first();
protected:
Queue<const BSTNode<Object> *> q;
};
}
#endif
//////////////////////////////////////////InvalidTreeArgument .cpp //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include "InvalidTreeArgument.h"
namespace cs20 {
InvalidTreeArgument::InvalidTreeArgument( const std::string& msg ) : std::logic_error( msg.c_str() ) {}
}
//////////////////////////////////////////BadIterator .cpp//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include "BadIterator.h"
namespace cs20 {
BadIterator::BadIterator( const std::string& msg ) : std::logic_error( msg.c_str() ) {}
}
//////////////////////////////////////////QueueNode .h//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#ifndef QUEUENODE_H
#define QUEUENODE_H
#include <iostream>
namespace cs20 {
template <class Object>
class QueueNode {
public:
QueueNode( const Object& theElement = Object(), QueueNode * node = nullptr );
// these accessors and mutators are called
// from Queue class
// no public methods expose QueueNode instances
// outside the Queue class
const Object& getElement() const;
QueueNode* getNext() const;
void setNext( QueueNode * node );
private:
Object element;
QueueNode* next;
};
}
#endif
//////////////////////////////////////////EmptyQueue .cpp//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include "EmptyQueue.h"
namespace cs20 {
EmptyQueue::EmptyQueue( const std::string& msg ) : std::logic_error( msg.c_str() ) {}
}
//////////////////////////////////////////EmptyQueue .h//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#ifndef EMPTYQUEUE_H
#define EMPTYQUEUE_H
#include <iostream>
#include <string>
namespace cs20 {
class EmptyQueue : public std::logic_error {
public:
EmptyQueue( const std::string& msg = "" );
};
}
#endif
Explanation / Answer
#include "BST.h"
namespace cs20 {
template <class Object>
BST<Object>::BST() {
root = nullptr;
}
template <class Object>
BST<Object>::BST( const BST<Object>& rhs ) {
root = nullptr;
*this = rhs;
}
template <class Object>
BST<Object>::BST( const Object& rootElement ) {
root = new BSTNode<Object>( rootElement );
}
template <class Object>
BST<Object>::~BST() {
makeEmpty();
}
template <class Object>
bool BST<Object>::isEmpty() const {
return( root == nullptr );
}
template <class Object>
void BST<Object>::makeEmpty() {
makeEmpty( root );
}
template <class Object>
void BST<Object>::makeEmpty( NodePtr & node ) {
if (node != nullptr) {
NodePtr l = node->getLeftSide();
NodePtr r = node->getRightSide();
makeEmpty( l );
makeEmpty( r );
delete node;
node = nullptr;
}
}
template <class Object>
int BST<Object>::size() const {
return( BSTNode<Object>::size( root ) );
}
template <class Object>
int BST<Object>::height() const {
return( BSTNode<Object>::height( root ) );
}
template <class Object>
const Object& BST<Object>::findMin() const throw(InvalidTreeArgument) {
if (root == nullptr)
throw InvalidTreeArgument();
return( findMin( root ) );
}
template <class Object>
const Object& BST<Object>::findMax() const throw(InvalidTreeArgument) {
if (root == nullptr)
throw InvalidTreeArgument();
return( findMax( root ) );
}
template <class Object>
const Object& BST<Object>::findMin( NodePtr node ) const {
while( node->getLeftSide() != nullptr ) {
node = node->getLeftSide();
}
return( node->getElement() );
}
template <class Object>
const Object& BST<Object>::findMax( NodePtr node ) const {
while( node->getRightSide() != nullptr ) {
node = node->getRightSide();
}
return( node->getElement() );
}
template <class Object>
const Object& BST<Object>::find( const Object& x ) const throw (InvalidTreeArgument) {
return( find( x, root ) );
}
template <class Object>
const Object& BST<Object>::find( const Object& x, NodePtr node ) const throw (InvalidTreeArgument) {
if (node == nullptr)
throw InvalidTreeArgument();
if (node->getElement() < x) {
return( find( x, node->getLeftSide() ) );
}
if (node->getElement() > x) {
return( find( x, node->getRightSide() ) );
}
return( node->getElement() );
}
template <class Object>
void BST<Object>::insert( const Object& x ) throw (InvalidTreeArgument) {
insert( x, root );
}
template <class Object>
void BST<Object>::insert( const Object& x, NodePtr& node ) throw (InvalidTreeArgument) {
if (node == nullptr) {
node = new BSTNode<Object>( x, nullptr, nullptr );
}
else if (x < node->element) {
insert( x, node->leftSide );
}
else if (x > node->element) {
insert( x, node->rightSide );
}
else
throw InvalidTreeArgument();
}
template <class Object>
void BST<Object>::removeMin() throw (InvalidTreeArgument) {
removeMin( root );
}
template <class Object>
void BST<Object>::removeMin( NodePtr& node ) throw (InvalidTreeArgument) {
if (node == nullptr) {
throw InvalidTreeArgument();
}
else if (node->leftSide != nullptr) {
removeMin( node->leftSide );
}
else {
NodePtr temp = node;
node = node->rightSide;
delete temp;
}
}
template <class Object>
void BST<Object>::remove( const Object& x ) throw (InvalidTreeArgument) {
remove( x, root );
}
template <class Object>
void BST<Object>::remove( const Object& x, NodePtr & node ) throw (InvalidTreeArgument) {
if (node == nullptr)
throw InvalidTreeArgument();
else if (x < node->element)
remove( x, node->leftSide );
else if (x > node->element)
remove( x, node->rightSide );
else if (node->leftSide != nullptr && node->rightSide != nullptr) {
// 2 children
node->element = findMin( node->rightSide );
removeMin( node->rightSide );
}
else {
NodePtr temp = node;
if (node->leftSide != nullptr) {
node = node->leftSide;
}
else {
node = node->rightSide;
}
delete temp;
}
}
template <class Object>
const BST<Object>& BST<Object>::operator =( const BST<Object>& rhs ) {
if (this != &rhs) {
makeEmpty();
if (rhs.root != nullptr)
root = rhs.root->duplicate();
}
return( *this );
}
template <class Object>
std::ostream& BST<Object>::printBST( std::ostream& outs ) const {
if (isEmpty())
outs << "Empty BST";
else
root->printBSTNode( outs );
outs << std::endl;
return( outs );
}
template <class Object>
BSTNode<Object>* BST<Object>::getRoot() const {
return( root );
}
}
#endif
#ifndef LEVELORDERITERATOR_CPP
#define LEVELORDERITERATOR_CPP
#include <iostream>
#include <cstddef>
#include "BSTIterator.h"
#include "LevelOrderIterator.h"
#include "Queue.h"
namespace cs20 {
template <class Object>
LevelOrderIterator<Object>::LevelOrderIterator( const BST<Object> & theTree ) : BSTIterator<Object>( theTree ) {
q.enqueue( this->root );
}
template <class Object>
LevelOrderIterator<Object>::~LevelOrderIterator() {
}
template <class Object>
void LevelOrderIterator<Object>::first( ) {
q.makeEmpty();
if (this->root != nullptr) {
q.enqueue( this->root );
advance();
}
}
template <class Object>
void LevelOrderIterator<Object>::advance( ) {
if (q.isEmpty()) {
if (this->current == nullptr)
throw BadIterator();
this->current = nullptr;
}
else {
this->current = q.dequeue();
if (this->current->getLeftSide() != nullptr)
q.enqueue( this->current->getLeftSide() );
if (this->current->getRightSide() != nullptr)
q.enqueue( this->current->getRightSide() );
}
}
}
#endif
#ifndef QUEUENODE_CPP
#define QUEUENODE_CPP
#include "QueueNode.h"
namespace cs20 {
template <class Object>
QueueNode<Object>::QueueNode( const Object& theElement,
QueueNode<Object> * node ) {
element = theElement;
next = node;
}
template <class Object>
const Object& QueueNode<Object>::getElement() const {
return( element );
}
template <class Object>
QueueNode<Object>* QueueNode<Object>::getNext() const {
return( next );
}
template <class Object>
void QueueNode<Object>::setNext( QueueNode<Object> * node ) {
next = node;
}
}
#endif
#define BSTNODE_CPP
#include "BSTNode.h"
namespace cs20 {
template <class Object>
BSTNode<Object>::BSTNode( const Object& theElement,
BSTNode<Object> * theLeftSide,
BSTNode<Object> * theRightSide,
int theSize) {
element = theElement;
rightSide = theRightSide;
leftSide = theLeftSide;
sz = theSize;
}
template <class Object>
int BSTNode<Object>::size( BSTNode<Object> * node ) {
if (node == nullptr )
return( 0 );
else
return( 1 + size( node->rightSide ) + size( node->leftSide ) );
}
template <class Object>
int BSTNode<Object>::height( BSTNode<Object> * node ) {
if (node == nullptr )
return( -1 );
else
return( 1 + max( height( node->leftSide ), height( node->rightSide ) ) );
}
template <class Object>
BSTNode<Object> * BSTNode<Object>::duplicate( ) const {
BSTNode<Object> * newNode = new BSTNode<Object>( element );
if (rightSide != nullptr) {
newNode->rightSide = rightSide->duplicate();
}
if (leftSide != nullptr) {
newNode->leftSide = leftSide->duplicate();
}
newNode->sz = sz;
return( newNode );
}
template <class Object>
std::ostream& BSTNode<Object>::printBSTNode( std::ostream& outs ) const {
Object o = element;
outs << o << " ";
if (leftSide != nullptr)
leftSide->printBSTNode( outs );
else
outs << "LSNULLPTR ";
if (rightSide != nullptr)
rightSide->printBSTNode( outs );
else
outs << "RSNULLPTR ";
outs << std::endl;
return( outs );
}
template <class Object>
int BSTNode<Object>::max( int a, int b ) {
int result = a;
if (b > a)
result = b;
return( result );
}
template <class Object>
const Object& BSTNode<Object>::getElement() const {
return( element );
}
template <class Object>
BSTNode<Object>* BSTNode<Object>::getLeftSide() const {
return( leftSide );
}
template <class Object>
BSTNode<Object>* BSTNode<Object>::getRightSide() const {
return( rightSide );
}
}
#endif
#include <iostream>
#include "BadIterator.h"
#include "InvalidTreeArgument.h"
#include "LevelOrderIterator.h"
#include "LevelOrderIterator.cpp"
#include "Queue.h"
#include "Queue.cpp"
#include "QueueNode.h"
#include "QueueNode.cpp"
#include "BST.h"
#include "BST.cpp"
#include "BSTIterator.h"
#include "BSTIterator.cpp"
#include "BSTNode.h"
#include "BSTNode.cpp"
using namespace std;
using namespace cs20;
enum CHOICE {MAKEEMPTY, ISEMPTY, SIZE, HEIGHT, QUIT, PRINT, PRINTNODE, LEVELORDER, INSERT, REMOVE, SETROOT, REMOVEMIN, FINDMIN, FINDMAX, FIND };
CHOICE menu();
void printTree( const BST<int>& t );
int main(int argc, char* argv[]) {
int value;
BST<int> tree;
BSTNode<int> * node = nullptr;
CHOICE choice;
do {
choice = menu();
switch( choice ) {
case MAKEEMPTY:
tree.makeEmpty();
node = nullptr;
break;
case ISEMPTY:
if (tree.isEmpty()) {
cout << "tree is empty" << endl;
}
else {
cout << "tree is not empty" << endl;
}
break;
case SIZE:
if (node == nullptr) {
cout << "You silly... the current node is NULL!" << endl;
}
else {
cout << "size of current node=" << BSTNode<int>::size( node ) << endl;
}
break;
case HEIGHT:
if (node == nullptr) {
cout << "You silly... the current node is NULL!" << endl;
}
else {
cout << "height of current node=" << BSTNode<int>::height( node ) << endl;
}
break;
case PRINT:
printTree( tree );
break;
case PRINTNODE:
if (node == nullptr) {
cout << "You silly... the current node is NULL!" << endl;
}
else {
value = node->getElement();
cout << "value of current node=" << value << endl;
}
break;
case INSERT:
try {
cout << "Enter a value to insert: ";
cin >> value;
tree.insert( value );
} catch( InvalidTreeArgument ita ) {
cout << "InvalidTreeArgument caught!" << endl;
}
break;
case REMOVE:
try {
cout << "Enter a value to remove: ";
cin >> value;
tree.remove( value );
} catch( InvalidTreeArgument ita ) {
cout << "InvalidTreeArgument caught!" << endl;
}
break;
case SETROOT:
cout << "Enter root value: ";
cin >> value;
tree = BST<int>( value );
node = tree.getRoot();
break;
case LEVELORDER:
try {
LevelOrderIterator<int> iter( tree );
iter.first();
while( iter.isValid() ) {
value = iter.retrieve();
cout << value << " ";
iter.advance();
}
cout << endl;
}
catch( BadIterator bi ) {
cout << "badIterator exception caught!" << endl;
}
break;
case FIND:
try {
cout << "Enter a value to find: ";
cin >> value;
tree.find( value );
cout << value << " was found somewhere..." << endl;
} catch( InvalidTreeArgument ita ) {
cout << "You silly... that wasn't found in the tree!" << endl;
}
break;
case FINDMIN:
try {
value = tree.findMin();
cout << value << " is the minimum data element in the tree" << endl;
} catch( InvalidTreeArgument ita ) {
cout << "InvalidTreeArgument caught!" << endl;
}
break;
case FINDMAX:
try {
value = tree.findMax();
cout << value << " is the maximum data element in the tree" << endl;
} catch( InvalidTreeArgument ita ) {
cout << "InvalidTreeArgument caught!" << endl;
}
break;
case REMOVEMIN:
try {
tree.removeMin();
} catch( InvalidTreeArgument ita ) {
cout << "InvalidTreeArgument caught!" << endl;
}
break;
case QUIT:
break;
}
} while (choice != QUIT);
return( 0 );
}
void printTree( const BST<int> & t ) {
t.printBST( cout );
}
CHOICE menu() {
char choice;
CHOICE result;
cout << "(M)akeEmpty I(s)Empty si(Z)e (H)eight setRoo(T) (P)rint printN(O)de le(V)elOrder (I)nsert (R)emove RemoveMin(Y) FindMi(N) FindMa(X) (F)ind (Q)uit: " << endl;
cin >> choice;
switch( choice ) {
case 'M':
case 'm':
result = MAKEEMPTY;
break;
case 'S':
case 's':
result = ISEMPTY;
break;
case 'Z':
case 'z':
result = SIZE;
break;
case 'H':
case 'h':
result = HEIGHT;
break;
case 'Q':
case 'q':
result = QUIT;
break;
case 'P':
case 'p':
result = PRINT;
break;
case 'O':
case 'o':
result = PRINTNODE;
break;
case 'T':
case 't':
result = SETROOT;
break;
case 'V':
case 'v':
result = LEVELORDER;
break;
case 'I':
case 'i':
result = INSERT;
break;
case 'R':
case 'r':
result = REMOVE;
break;
case 'Y':
case 'y':
result = REMOVEMIN;
break;
case 'N':
case 'n':
result = FINDMIN;
break;
case 'X':
case 'x':
result = FINDMAX;
break;
case 'F':
case 'f':
result = FIND;
break;
}
return( result );
}
#ifndef BST_H
#define BST_H
// pragma for Visual Studio's lack of support for checked exceptions
#pragma warning( disable: 4290)
#include <iostream>
#include <cstddef>
#include "BSTNode.h"
#include "InvalidTreeArgument.h"
namespace cs20 {
template <class Object>
class BSTIterator;
template <class Object>
class BST {
public:
BST();
BST( const Object& rootElement );
BST( const BST& rhs );
~BST();
bool isEmpty() const;
void makeEmpty();
int size() const;
int height() const;
const Object& find( const Object& x ) const throw (InvalidTreeArgument);
const Object& findMin() const throw (InvalidTreeArgument);
const Object& findMax() const throw (InvalidTreeArgument);
void insert( const Object& x ) throw (InvalidTreeArgument);
void remove( const Object& x ) throw (InvalidTreeArgument);
void removeMin() throw (InvalidTreeArgument);
const BST& operator =( const BST& rhs );
std::ostream& printBST( std::ostream& outs ) const;
BSTNode<Object>* getRoot() const;
private:
typedef BSTNode<Object>* NodePtr;
NodePtr root;
void makeEmpty( NodePtr &t );
friend class BSTIterator<Object>;
const Object& find( const Object& x, NodePtr node ) const throw (InvalidTreeArgument);
const Object& findMin( NodePtr node ) const;
const Object& findMax( NodePtr node ) const;
void insert( const Object& x, NodePtr & node ) throw (InvalidTreeArgument);
void remove( const Object& x, NodePtr & node ) throw (InvalidTreeArgument);
void removeMin( NodePtr & node ) throw (InvalidTreeArgument);
};
}
#endif
#ifndef BSTNODE_H
#define BSTNODE_H
#include <iostream>
namespace cs20 {
template <class Object>
class BST;
template <class Object>
class BSTNode {
public:
BSTNode( const Object& theElement = Object(),
BSTNode * theLeftSide = nullptr,
BSTNode * theRightSide = nullptr,
int theSize = 1);
BSTNode * duplicate() const;
static int size( BSTNode * t );
static int height( BSTNode * t );
const Object& getElement() const;
BSTNode* getLeftSide() const;
BSTNode* getRightSide() const;
std::ostream& printBSTNode ( std::ostream& outs ) const;
friend class BST<Object>;
private:
Object element;
BSTNode* rightSide;
BSTNode* leftSide;
int sz;
static int max( int a, int b );
};
}
#endif
#ifndef QUEUE_CPP
#define QUEUE_CPP
#include "Queue.h"
namespace cs20 {
template <class Object>
Queue<Object>::Queue() {
frontNode = nullptr;
backNode = nullptr;
}
template <class Object>
Queue<Object>::Queue( const Queue<Object>& rhs ) {
frontNode = nullptr;
backNode = nullptr;
*this = rhs;
}
template <class Object>
Queue<Object>::~Queue() {
makeEmpty();
}
template <class Object>
bool Queue<Object>::isEmpty() const {
return( (frontNode == nullptr) );
}
template <class Object>
void Queue<Object>::makeEmpty() {
while (!isEmpty()) {
dequeue();
}
}
template <class Object>
void Queue<Object>::enqueue( const Object& data ) {
QueueNode<Object>* newNode = new QueueNode<Object>( data );
if (isEmpty()) {
frontNode = newNode;
backNode = newNode;
}
else {
backNode->setNext( newNode );
backNode = backNode->getNext();
}
}
template <class Object>
const Object Queue<Object>::dequeue() {
Object frontData = getFront();
QueueNode<Object> * oldFront = frontNode;
frontNode = frontNode->getNext();
delete oldFront;
return( frontData );
}
template <class Object>
const Object& Queue<Object>::getFront() const {
if (isEmpty()) {
throw EmptyQueue();
}
return( frontNode->getElement() );
}
// Deep copy of linked Queue
template <class Object>
const Queue<Object>& Queue<Object>::operator =( const Queue<Object>& rhs ) {
if (this != &rhs) {
makeEmpty();
QueueNode<Object> * rhsFrontNode = rhs.frontNode;
while( rhsFrontNode != nullptr) {
enqueue( rhsFrontNode->getElement() );
rhsFrontNode = rhsFrontNode->getNext();
}
}
return( *this );
}
template <class Object>
std::ostream& Queue<Object>::printQueue( std::ostream& outs ) {
if (isEmpty()) {
outs << "Empty Queue";
}
else {
QueueNode<Object> * node = frontNode;
while( node != nullptr) {
outs << node->getElement();
outs << " ";
node = node->getNext();
}
}
return( outs );
}
}
#endif
#ifndef QUEUE_H
#define QUEUE_H
#include <iostream>
#include "QueueNode.h"
#include "EmptyQueue.h"
namespace cs20 {
template <class Object>
class Queue {
public:
Queue();
Queue( const Queue& rhs );
~Queue();
bool isEmpty() const;
void makeEmpty();
void enqueue( const Object& data );
const Object dequeue();
const Object& getFront() const;
const Queue& operator =( const Queue& rhs );
std::ostream& printQueue( std::ostream& outs );
private:
QueueNode<Object> * frontNode;
QueueNode<Object> * backNode;
};
}
#endif
#ifndef BADITERATOR_H
#define BADITERATOR_H
#include <iostream>
#include <string>
#include <stdexcept>
namespace cs20 {
class BadIterator : public std::logic_error {
public:
BadIterator( const std::string& msg = "" );
};
}
#endif
#ifndef INVALIDTREEARGUMENT_H
#define INVALIDTREEARGUMENT_H
#include <iostream>
#include <string>
#include <stdexcept>
namespace cs20 {
class InvalidTreeArgument : public std::logic_error {
public:
InvalidTreeArgument( const std::string& msg = "" );
};
}
#endif
#ifndef BSTITERATOR_CPP
#define BSTITERATOR_CPP
#include "BSTIterator.h"
namespace cs20 {
template <class Object>
BSTIterator<Object>::BSTIterator( const BST<Object> & theTree ) : root( theTree.root ) , current( nullptr ) {
}
template <class Object>
BSTIterator<Object>::~BSTIterator() {
}
template <class Object>
bool BSTIterator<Object>::isValid( ) const {
return( (current != nullptr) );
}
template <class Object>
const Object& BSTIterator<Object>::retrieve( ) const {
if (!(isValid())) throw BadIterator();
return( current->getElement() );
}
}
#endif
#ifndef BSTITERATOR_H
#define BSTITERATOR_H
#include <iostream>
#include "BSTNode.h"
#include "BST.h"
#include "BadIterator.h"
namespace cs20 {
template <class Object>
class BSTIterator {
public:
BSTIterator( const BST<Object>& theTree );
virtual ~BSTIterator();
bool isValid() const;
virtual void advance() = 0;
virtual void first() = 0;
const Object& retrieve() const;
protected:
const BSTNode<Object> * current;
const BSTNode<Object> * root;
};
}
#endif
#ifndef LEVELORDERITERATOR_H
#define LEVELORDERITERATOR_H
#include <iostream>
#include "BST.h"
#include "BSTIterator.h"
#include "Queue.h"
namespace cs20 {
template <class Object>
class LevelOrderIterator : public BSTIterator<Object> {
public:
LevelOrderIterator( const BST<Object>& theTree );
virtual ~LevelOrderIterator();
void advance();
void first();
protected:
Queue<const BSTNode<Object> *> q;
};
}
#
#include "InvalidTreeArgument.h"
namespace cs20 {
InvalidTreeArgument::InvalidTreeArgument( const std::string& msg ) : std::logic_error( msg.c_str() ) {}
}
#include "BadIterator.h"
namespace cs20 {
BadIterator::BadIterator( const std::string& msg ) : std::logic_error( msg.c_str() ) {}
}
#ifndef QUEUENODE_H
#define QUEUENODE_H
#include <iostream>
namespace cs20 {
template <class Object>
class QueueNode {
public:
QueueNode( const Object& theElement = Object(), QueueNode * node = nullptr );
const Object& getElement() const;
QueueNode* getNext() const;
void setNext( QueueNode * node );
private:
Object element;
QueueNode* next;
};
}
#endif
#include "EmptyQueue.h"
namespace cs20 {
EmptyQueue::EmptyQueue( const std::string& msg ) : std::logic_error( msg.c_str() ) {}
}
#include <iostream>
#include <string>
namespace cs20 {
class EmptyQueue : public std::logic_error {
public:
EmptyQueue( const std::string& msg = "" );
};
}
#endif
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.