As you may recall, the implementation of the cs20::BinaryTree< Object > data str
ID: 3837392 • Letter: A
Question
As you may recall, the implementation of the cs20::BinaryTree< Object > data structure presented in class used a left-child/right-child node structure. Based on this data structure, write the following method:
This method should attempt to locate the Object a inside the tree. If every time a is found it is held in a treenode with a size of 3, your method should return true; otherwise, return false. If the root of this BinaryTree is NULL, your code should throw InvalidTreeArgument.
For example, consider the BinaryTree t shown below:
t.alwaysHasSize3( 12 ); should return false since 12 is not located inside this tree
t.alwaysHasSize3( 17 ); should return true because every node holding 17 has a size of 3
t.alwaysHasSize3( 30 ); should return false since there is a node holding 30 that does not have size 3
Feel free to define any public or private methods or members on the class BinaryTree<Object> as you need. Please work with the code from class.
HINT: This is a method of the BinaryTree class. Also feel free to use recursion. It might be much easier to think about this problem from the following point of view: "if Object a is not found at all, return false. Otherwise, return true when every treenode holding Object a has size 3."
BinaryTreeNode.h
#ifndef BINARYTREENODE_H
#define BINARYTREENODE_H
#include <iostream>
#include <cstddef>
namespace cs20 {
template <class Object>
class BinaryTreeNode {
public:
BinaryTreeNode( const Object& theElement = Object(),
BinaryTreeNode * theLeftSide = nullptr,
BinaryTreeNode * theRightSide = nullptr);
BinaryTreeNode * duplicate() const;
static int size( BinaryTreeNode * t );
static int height( BinaryTreeNode * t );
// no references to a BinaryTreeNode are returned
// publicly by either BinaryTree or BinaryTreeIterator
// these methods are only called by BinaryTree and
// BinaryTreeIterator
const Object& getElement() const;
BinaryTreeNode* getLeftSide() const;
BinaryTreeNode* getRightSide() const;
void setLeftSide( BinaryTreeNode* node );
void setRightSide( BinaryTreeNode* node );
private:
Object element;
BinaryTreeNode* rightSide;
BinaryTreeNode* leftSide;
};
}
#endif
/////////////////////////////////////////////////////////////////////////////////////
BinaryTreeNode.cpp
#ifndef BINARYTREENODE_CPP
#define BINARYTREENODE_CPP
#include "BinaryTreeNode.h"
namespace cs20 {
template <class Object>
BinaryTreeNode<Object>::BinaryTreeNode( const Object& theElement,
BinaryTreeNode<Object> * theLeftSide,
BinaryTreeNode<Object> * theRightSide ) {
element = theElement;
rightSide = theRightSide;
leftSide = theLeftSide;
}
template <class Object>
int BinaryTreeNode<Object>::size( BinaryTreeNode<Object> * node ) {
if (node == nullptr )
return( 0 );
else
return( 1 + size( node->rightSide ) + size( node->leftSide ) );
}
template <class Object>
int BinaryTreeNode<Object>::height( BinaryTreeNode<Object> * node ) {
if (node == nullptr )
return( -1 );
else
return( 1 + std::max( height( node->leftSide ), height( node->rightSide ) ) );
}
template <class Object>
BinaryTreeNode<Object> * BinaryTreeNode<Object>::duplicate( ) const {
BinaryTreeNode<Object> * newNode = new BinaryTreeNode<Object>( element );
if (rightSide != nullptr) {
newNode->rightSide = rightSide->duplicate();
}
if (leftSide != nullptr) {
newNode->leftSide = leftSide->duplicate();
}
return( newNode );
}
template <class Object>
const Object& BinaryTreeNode<Object>::getElement() const {
return( element );
}
template <class Object>
BinaryTreeNode<Object>* BinaryTreeNode<Object>::getLeftSide() const {
return( leftSide );
}
template <class Object>
BinaryTreeNode<Object>* BinaryTreeNode<Object>::getRightSide() const {
return( rightSide );
}
template <class Object>
void BinaryTreeNode<Object>::setLeftSide( BinaryTreeNode<Object>* node ) {
leftSide = node;
}
template <class Object>
void BinaryTreeNode<Object>::setRightSide( BinaryTreeNode<Object>* node ) {
rightSide = node;
}
}
#endif
/////////////////////////////////////////////////////////////////////////////////////
LevelOrderIterator.cpp
#ifndef LEVELORDERITERATOR_CPP
#define LEVELORDERITERATOR_CPP
#include "LevelOrderIterator.h"
namespace cs20 {
template <class Object>
LevelOrderIterator<Object>::LevelOrderIterator( const BinaryTree<Object> & theTree ) : BinaryTreeIterator<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 (current->leftSide != nullptr)
// q.enqueue( current->leftSide );
//if (current->rightSide != nullptr)
// q.enqueue( current->rightSide );
if (this->current->getLeftSide() != nullptr)
q.enqueue( this->current->getLeftSide() );
if (this->current->getRightSide() != nullptr)
q.enqueue( this->current->getRightSide() );
}
}
}
#endif
/////////////////////////////////////////////////////////////////////////////////////
BinaryTree.cpp
#ifndef BINARYTREE_CPP
#define BINARYTREE_CPP
#include "BinaryTree.h"
namespace cs20 {
template <class Object>
BinaryTree<Object>::BinaryTree() {
root = nullptr;
}
template <class Object>
BinaryTreeNode<Object> * BinaryTree<Object>::getRoot() const {
return( root );
}
template <class Object>
BinaryTree<Object>::BinaryTree( const BinaryTree<Object>& rhs ) {
root = nullptr;
*this = rhs;
}
template <class Object>
BinaryTree<Object>::BinaryTree( const Object& rootElement ) {
root = new BinaryTreeNode<Object>( rootElement );
}
template <class Object>
BinaryTree<Object>::~BinaryTree() {
makeEmpty();
}
template <class Object>
bool BinaryTree<Object>::isEmpty() const {
return( root == nullptr );
}
template <class Object>
void BinaryTree<Object>::makeEmpty() {
makeEmpty( root );
}
template <class Object>
void BinaryTree<Object>::makeEmpty( NodePtr & node ) {
if (node != nullptr) {
NodePtr r = node->getRightSide();
NodePtr l = node->getLeftSide();
if (r != nullptr)
makeEmpty( r );
if (l != nullptr)
makeEmpty( l );
delete node;
node = nullptr;
}
}
template <class Object>
int BinaryTree<Object>::size() const {
return( BinaryTreeNode<Object>::size( root ) );
}
template <class Object>
int BinaryTree<Object>::height() const {
return( BinaryTreeNode<Object>::height( root ) );
}
template <class Object>
void BinaryTree<Object>::setRightSide( BinaryTree& theRightSide ) {
if (theRightSide.root == nullptr)
throw( InvalidTreeArgument() );
BinaryTreeNode<Object> *child = new BinaryTreeNode<Object>( theRightSide.root->getElement(),
theRightSide.root->getLeftSide(),
theRightSide.root->getRightSide() );
root->setRightSide( child );
if (child != theRightSide.root)
theRightSide.root = nullptr;
}
template <class Object>
void BinaryTree<Object>::setLeftSide( BinaryTree& theLeftSide ) {
if (theLeftSide.root == nullptr)
throw( InvalidTreeArgument() );
BinaryTreeNode<Object> *child = new BinaryTreeNode<Object>( theLeftSide.root->getElement(),
theLeftSide.root->getLeftSide(),
theLeftSide.root->getRightSide() );
root->setLeftSide( child );
if (child != theLeftSide.root)
theLeftSide.root = nullptr;
}
template <class Object>
void BinaryTree<Object>::merge( const Object& rootElement,
BinaryTree & left,
BinaryTree & right ) {
if ( left.root == right.root && left.root != nullptr ) {
std::cerr << "Cannot merge a tree with itself" << std::endl;
throw( InvalidTreeArgument() );
}
else {
NodePtr oldRoot = root;
root = new BinaryTreeNode<Object>( rootElement,
left.root,
right.root );
if (this != &left && this != &right)
makeEmpty( oldRoot );
if (this != &left)
left.root = nullptr;
if (this != &right)
right.root = nullptr;
}
}
// Deep copy of tree
template <class Object>
const BinaryTree<Object>& BinaryTree<Object>::operator =( const BinaryTree<Object>& rhs ) {
if (this != &rhs) {
makeEmpty();
if (rhs.root != nullptr)
root = rhs.root->duplicate();
}
return( *this );
}
template <class Object>
void BinaryTree<Object>::printTree( std::ostream& out ) const {
if (root == nullptr) {
out << "nullptr" << std::endl;
}
else {
printTree( root, out );
out << std::endl;
}
}
template <class Object>
void BinaryTree<Object>::printTree( NodePtr subtree, std::ostream & out ) const {
if (subtree == nullptr) {
out << "nullptr";
}
else {
out << subtree->getElement();
out << " ";
printTree( subtree->getLeftSide(), out );
out << " ";
printTree( subtree->getRightSide(), out );
out << " ";
}
}
}
#endif
/////////////////////////////////////////////////////////////////////////////////////
BinaryTreeIterator.h
#ifndef BINARYTREEITERATOR_H
#define BINARYTREEITERATOR_H
#include <iostream>
#include "BinaryTreeNode.h"
#include "BinaryTree.h"
#include "BadIterator.h"
namespace cs20 {
template <class Object>
class BinaryTreeIterator {
public:
BinaryTreeIterator( const BinaryTree<Object>& theTree );
virtual ~BinaryTreeIterator();
bool isValid() const;
virtual void advance() = 0;
virtual void first() = 0;
const Object& retrieve() const;
//protected:
const BinaryTreeNode<Object> * current;
const BinaryTreeNode<Object> * root;
};
}
#endif
/////////////////////////////////////////////////////////////////////////////////////
TreeMenu.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 "BinaryTree.h"
#include "BinaryTree.cpp"
#include "BinaryTreeIterator.h"
#include "BinaryTreeIterator.cpp"
#include "BinaryTreeNode.h"
#include "BinaryTreeNode.cpp"
using namespace std;
using namespace cs20;
enum CHOICE {MAKEEMPTY, ISEMPTY, SIZE, HEIGHT, QUIT, PRINT, PRINTNODE, LEVELORDER, SETROOT, SETLEFT, SETRIGHT, GOTOROOT, GOLEFT, GORIGHT };
CHOICE menu();
void printTree( const BinaryTree<int>& t );
int main(int argc, char* argv[]) {
int value;
BinaryTree<int> tree;
BinaryTreeNode<int> * node = nullptr;
BinaryTree<int> lefttree;
BinaryTree<int> righttree;
BinaryTreeNode<int> * leftnode = nullptr;
BinaryTreeNode<int> * rightnode = 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 nullptr!" << endl;
}
else {
cout << "size of current node=" << BinaryTreeNode<int>::size( node ) << endl;
}
break;
case HEIGHT:
if (node == nullptr) {
cout << "You silly... the current node is nullptr!" << endl;
}
else {
cout << "height of current node=" << BinaryTreeNode<int>::height( node ) << endl;
}
break;
case PRINT:
printTree( tree );
break;
case PRINTNODE:
if (node == nullptr) {
cout << "You silly... the current node is nullptr!" << endl;
}
else {
value = node->getElement();
cout << "value of current node=" << value << endl;
}
break;
case SETLEFT:
try {
cout << "Enter a value for node's leftside: ";
cin >> value;
leftnode = new BinaryTreeNode<int>( value );
node->setLeftSide( leftnode );
} catch( InvalidTreeArgument ita ) {
cout << "InvalidTreeArgument caught!" << endl;
}
break;
case SETRIGHT:
try {
cout << "Enter a value for node's rightside: ";
cin >> value;
rightnode = new BinaryTreeNode<int>( value );
node->setRightSide( rightnode );
} catch( InvalidTreeArgument ita ) {
cout << "InvalidTreeArgument caught!" << endl;
}
break;
case SETROOT:
cout << "Enter root value: ";
cin >> value;
// not sure this is too clever...
tree = BinaryTree<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 GOTOROOT:
node = tree.getRoot();
break;
case GOLEFT:
node = node->getLeftSide();
break;
case GORIGHT:
node = node->getRightSide();
break;
case QUIT:
break;
}
} while (choice != QUIT);
return( 0 );
}
void printTree( const BinaryTree<int> & t ) {
t.printTree( cout );
}
CHOICE menu() {
char choice;
CHOICE result;
cout << "(M)akeEmpty (I)sEmpty (S)ize (H)eight setRoo(T) set(L)eftSide set(R)ightSide gotoroot(1) gole(F)t gori(G)ht (P)rint printN(O)de le(V)elOrder (Q)uit: " << endl;
cin >> choice;
switch( choice ) {
case 'M':
case 'm':
result = MAKEEMPTY;
break;
case 'S':
case 's':
result = SIZE;
break;
case 'I':
case 'i':
result = ISEMPTY;
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 'L':
case 'l':
result = SETLEFT;
break;
case 'R':
case 'r':
result = SETRIGHT;
break;
case 'F':
case 'f':
result = GOLEFT;
break;
case 'G':
case 'g':
result = GORIGHT;
break;
case '1':
result = GOTOROOT;
break;
}
return( result );
}
/////////////////////////////////////////////////////////////////////////////////////
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;
}
template <class Object>
std::ostream& operator <<( std::ostream& outs, const QueueNode<Object> * node ) {
if (node == nullptr) {
outs << "Empty Queue";
}
else {
QueueNode<Object> current = *node;
// yucky loop, but I did not want to build a
// constructor, destructor and equal operator
// for a QueueNode
while( true ) {
Object o = current.element;
outs << o << " ";
if (current.next == nullptr)
break;
else
current = *(current.next);
}
}
outs << std::endl;
return( outs );
}
}
#endif
/////////////////////////////////////////////////////////////////////////////////////
BinaryTree.h
#ifndef BINARYTREE_H
#define BINARYTREE_H
#include <iostream>
#include <cstddef>
#include "BinaryTreeNode.h"
#include "InvalidTreeArgument.h"
namespace cs20 {
template <class Object>
class BinaryTreeIterator;
template <class Object>
class BinaryTree {
public:
BinaryTree();
BinaryTree( const Object& rootElement );
BinaryTree( const BinaryTree& rhs );
~BinaryTree();
bool isEmpty() const;
void makeEmpty();
int size() const;
int height() const;
void merge( const Object& rootElement,
BinaryTree& firstChild,
BinaryTree& nextSibling );
void setRightSide( BinaryTree& theRightSide );
void setLeftSide( BinaryTree& theLeftSide );
const BinaryTree& operator =( const BinaryTree& rhs );
// this is tremendously bad form but I had to do it
// to support the menu-based program
BinaryTreeNode<Object> * getRoot() const;
void printTree( std::ostream& out ) const;
private:
typedef BinaryTreeNode<Object>* NodePtr;
NodePtr root;
void makeEmpty( NodePtr &t );
friend class BinaryTreeIterator<Object>;
void printTree( NodePtr subtree, std::ostream & out ) const;
};
}
#endif
/////////////////////////////////////////////////////////////////////////////////////
BinaryTreeIterator.cpp
#ifndef BINARYTREEITERATOR_CPP
#define BINARYTREEITERATOR_CPP
#include "BinaryTreeIterator.h"
namespace cs20 {
template <class Object>
BinaryTreeIterator<Object>::BinaryTreeIterator( const BinaryTree<Object> & theTree ) : root( theTree.root ) , current( nullptr ) {
// all assignments performed thru code above
}
template <class Object>
BinaryTreeIterator<Object>::~BinaryTreeIterator() {
}
template <class Object>
bool BinaryTreeIterator<Object>::isValid( ) const {
return( (current != nullptr) );
}
template <class Object>
const Object& BinaryTreeIterator<Object>::retrieve( ) const {
if (!(isValid())) throw BadIterator();
return( current->getElement() );
}
}
#endif
/////////////////////////////////////////////////////////////////////////////////////
LevelOrderIterator.h
#ifndef LEVELORDERITERATOR_H
#define LEVELORDERITERATOR_H
#include <iostream>
#include <cstddef>
#include "BinaryTree.h"
#include "BinaryTreeIterator.h"
#include "Queue.h"
namespace cs20 {
template <class Object>
class LevelOrderIterator : public BinaryTreeIterator<Object> {
public:
LevelOrderIterator( const BinaryTree<Object>& theTree );
virtual ~LevelOrderIterator();
void advance();
void first();
protected:
Queue<const BinaryTreeNode<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() ) {}
}
/////////////////////////////////////////////////////////////////////////////////////
InvalidTreeArgument.h
#ifndef INVALIDTREEARGUMENT_H
#define INVALIDTREEARGUMENT_H
#include <iostream>
#include <string>
namespace cs20 {
class InvalidTreeArgument : public std::logic_error {
public:
InvalidTreeArgument( const std::string& msg = "" );
};
}
#endif
/////////////////////////////////////////////////////////////////////////////////////
BadIterator.h
#ifndef BADITERATOR_H
#define BADITERATOR_H
#include <iostream>
#include <string>
namespace cs20 {
class BadIterator : public std::logic_error {
public:
BadIterator( const std::string& msg = "" );
};
}
#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 nullptr
}
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& operator << ( std::ostream& outs, const Queue<Object>& q ) {
outs << q.frontNode;
return( outs );
}
template <class Object>
std::ostream& operator << ( std::ostream& outs, const Queue<Object>* q ) {
outs << q->frontNode;
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 );
// take this out for the student version
friend std::ostream& operator << ( std::ostream& outs, const Queue& q );
friend std::ostream& operator << ( std::ostream& outs, const Queue* q );
private:
QueueNode<Object> * frontNode;
QueueNode<Object> * backNode;
};
}
#endif
/////////////////////////////////////////////////////////////////////////////////////
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 );
friend std::ostream& operator <<( std::ostream& outs, const QueueNode * node );
// 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
88 26 30 30 40Explanation / Answer
BinaryTree.cpp
#ifndef BINARYTREE_CPP
#define BINARYTREE_CPP
#include "BinaryTree.h"
#include "BinaryTreeNode.h"
#include "InvalidTreeArgument.h"
namespace cs20 {
template <class Object>
BinaryTree<Object>::BinaryTree() {
root = nullptr;
}
template <class Object>
BinaryTreeNode<Object> * BinaryTree<Object>::getRoot() const {
return( root );
}
template <class Object>
BinaryTree<Object>::BinaryTree( const BinaryTree<Object>& rhs ) {
root = nullptr;
*this = rhs;
}
template <class Object>
BinaryTree<Object>::BinaryTree( const Object& rootElement ) {
root = new BinaryTreeNode<Object>( rootElement );
}
template <class Object>
BinaryTree<Object>::~BinaryTree() {
makeEmpty();
}
/* Question 24 */
///////////////////////////////////////////////////////////////////////////
// alwaysHasSize3
///////////////////////////////////////////////////////////////////////////
template <class Object>
bool BinaryTree<Object>::alwaysHasSize3( Object a ) const throw( InvalidTreeArgument )
{
if ( isEmpty() )
{
throw( InvalidTreeArgument() );
}
return( alwaysHasSize3( this->root , a ) );
}
template <class Object>
bool BinaryTree<Object>::alwaysHasSize3( BinaryTreeNode< Object > * node, Object a ) const throw( InvalidTreeArgument )
{
bool result = false;
if ( node != nullptr )
{
if ( node->getElement() == a )
{
if ( BinaryTreeNode<Object>::size( node ) == 3 )
{
result = true;
}
else
{
result = false;
}
}
if ( node->getLeftSide( ) != nullptr)
{
result = result || alwaysHasSize3( node->getLeftSide( ), a );
}
if ( node->getRightSide( ) != nullptr )
{
result = result || alwaysHasSize3( node->getRightSide( ), a );
}
}
return( result );
}
/* ----------------------------------------------------------------------- */
template <class Object>
bool BinaryTree<Object>::isEmpty() const {
return( root == nullptr );
}
template <class Object>
void BinaryTree<Object>::makeEmpty() {
makeEmpty( root );
}
template <class Object>
void BinaryTree<Object>::makeEmpty( NodePtr & node ) {
if (node != nullptr) {
NodePtr r = node->getRightSide();
NodePtr l = node->getLeftSide();
if (r != nullptr)
makeEmpty( r );
if (l != nullptr)
makeEmpty( l );
delete node;
node = nullptr;
}
}
template <class Object>
int BinaryTree<Object>::size() const {
return( BinaryTreeNode<Object>::size( root ) );
}
template <class Object>
int BinaryTree<Object>::height() const {
return( BinaryTreeNode<Object>::height( root ) );
}
template <class Object>
void BinaryTree<Object>::setRightSide( BinaryTree& theRightSide ) {
if (theRightSide.root == nullptr)
throw( InvalidTreeArgument() );
BinaryTreeNode<Object> *child = new BinaryTreeNode<Object>( theRightSide.root->getElement(),
theRightSide.root->getLeftSide(),
theRightSide.root->getRightSide() );
root->setRightSide( child );
if (child != theRightSide.root)
theRightSide.root = nullptr;
}
template <class Object>
void BinaryTree<Object>::setLeftSide( BinaryTree& theLeftSide ) {
if (theLeftSide.root == nullptr)
throw( InvalidTreeArgument() );
BinaryTreeNode<Object> *child = new BinaryTreeNode<Object>( theLeftSide.root->getElement(),
theLeftSide.root->getLeftSide(),
theLeftSide.root->getRightSide() );
root->setLeftSide( child );
if (child != theLeftSide.root)
theLeftSide.root = nullptr;
}
template <class Object>
void BinaryTree<Object>::merge( const Object& rootElement,
BinaryTree & left,
BinaryTree & right ) {
if ( left.root == right.root && left.root != nullptr ) {
std::cerr << "Cannot merge a tree with itself" << std::endl;
throw( InvalidTreeArgument() );
}
else {
NodePtr oldRoot = root;
root = new BinaryTreeNode<Object>( rootElement,
left.root,
right.root );
if (this != &left && this != &right)
makeEmpty( oldRoot );
if (this != &left)
left.root = nullptr;
if (this != &right)
right.root = nullptr;
}
}
// Deep copy of tree
template <class Object>
const BinaryTree<Object>& BinaryTree<Object>::operator =( const BinaryTree<Object>& rhs ) {
if (this != &rhs) {
makeEmpty();
if (rhs.root != nullptr)
root = rhs.root->duplicate();
}
return( *this );
}
template <class Object>
void BinaryTree<Object>::printTree( std::ostream& out ) const {
if (root == nullptr) {
out << "nullptr" << std::endl;
}
else {
printTree( root, out );
out << std::endl;
}
}
template <class Object>
void BinaryTree<Object>::printTree( NodePtr subtree, std::ostream & out ) const {
if (subtree == nullptr) {
out << "nullptr";
}
else {
out << subtree->getElement();
out << " ";
printTree( subtree->getLeftSide(), out );
out << " ";
printTree( subtree->getRightSide(), out );
out << " ";
}
}
}
#endif
BinaryTree.h
#ifndef BINARYTREE_H
#define BINARYTREE_H
#include <iostream>
#include <cstddef>
#include "BinaryTreeNode.h"
#include "InvalidTreeArgument.h"
#pragma warning( disable : 4290 )
namespace cs20 {
template <class Object>
class BinaryTreeIterator;
template <class Object>
class BinaryTree {
public:
BinaryTree();
BinaryTree( const Object& rootElement );
BinaryTree( const BinaryTree& rhs );
~BinaryTree();
bool isEmpty() const;
void makeEmpty();
int size() const;
int height() const;
void merge( const Object& rootElement,
BinaryTree& firstChild,
BinaryTree& nextSibling );
void setRightSide( BinaryTree& theRightSide );
void setLeftSide( BinaryTree& theLeftSide );
const BinaryTree& operator =( const BinaryTree& rhs );
BinaryTreeNode<Object> * getRoot() const;
void printTree( std::ostream& out ) const;
/* Question 24 */
bool alwaysHasSize3( Object a ) const throw( InvalidTreeArgument );
private:
typedef BinaryTreeNode<Object>* NodePtr;
NodePtr root;
void makeEmpty( NodePtr &t );
friend class BinaryTreeIterator<Object>;
void printTree( NodePtr subtree, std::ostream & out ) const;
/* Question 24 */
bool alwaysHasSize3( BinaryTreeNode< Object > * node, Object a ) const throw( InvalidTreeArgument );
};
}
#endif
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.