don\'t think you guys need to copy all of the classes but i\'ve provided all of
ID: 3828793 • Letter: D
Question
don't think you guys need to copy all of the classes but i've provided all of them just in case!!!!!!!!!!!!!
Project 3A : Working With First-Child Next-Sibling Tree Representation
Complete the following exercises using the cs20::Tree class presented in class.
1. Implement either a PreOrder or PostOrder TreeIterator class using the TreeIterator class as the base class of the class you create.
2. Without using a TreeIterator, create a new method called level that takes no arguments and calculates the level value for this binary tree. Recall that the level value for a tree will match the greatest level value of any node in the tree. If the root of the tree is NULL, your method should throw the InvalidTreeArgument exception. The prototype for this method should be:
int level() throw (InvalidTreeArgument);
Create a test driver that exercises each of these additional features, prints the tree and the results of each new operation.
Tree.cpp
#ifndef TREE_CPP
#define TREE_CPP
#include <iostream>
#include <cstddef>
#include "Tree.h"
#include "TreeNode.h"
#include "InvalidTreeArgument.h"
namespace cs20 {
template <class Object>
Tree<Object>::Tree() {
root = nullptr;
}
template <class Object>
Tree<Object>::Tree( const Tree<Object>& rhs ) {
root = nullptr;
*this = rhs;
}
template <class Object>
Tree<Object>::Tree( const Object& rootElement ) {
root = new TreeNode<Object>( rootElement );
}
template <class Object>
Tree<Object>::~Tree() {
makeEmpty();
}
template <class Object>
const Object & Tree<Object>::getElement() const {
return( root->getElement() );
}
template <class Object>
bool Tree<Object>::isEmpty() const {
return( root == nullptr );
}
template <class Object>
void Tree<Object>::makeEmpty() {
makeEmpty( root );
}
template <class Object>
TreeNode<Object> * Tree<Object>::getFirstChild( ) const {
return( root->getFirstChild() );
}
template <class Object>
TreeNode<Object> * Tree<Object>::getNextSibling( ) const {
return( root->getNextSibling() );
}
template <class Object>
TreeNode<Object> * Tree<Object>::getRoot( ) const {
return( root );
}
template <class Object>
void Tree<Object>::makeEmpty( NodePtr & node ) {
if (node != nullptr) {
NodePtr fc = node->getFirstChild();
NodePtr ns = node->getNextSibling();
if (fc != nullptr)
makeEmpty( fc );
if (ns != nullptr)
makeEmpty( ns );
delete node;
node = nullptr;
}
}
template <class Object>
int Tree<Object>::size() const {
return( TreeNode<Object>::size( root ) );
}
template <class Object>
int Tree<Object>::height() const {
return( TreeNode<Object>::height( root ) );
}
template <class Object>
void Tree<Object>::setFirstChild( Tree& theFirstChild ) {
if (theFirstChild.root == nullptr)
throw( InvalidTreeArgument() );
TreeNode<Object> *child = new TreeNode<Object>( theFirstChild.root->getElement(),
theFirstChild.root->getFirstChild(),
theFirstChild.root->getNextSibling() );
root->setFirstChild( child );
if (child != theFirstChild.root)
theFirstChild.root = nullptr;
}
template <class Object>
void Tree<Object>::setNextSibling( Tree& theNextSibling ) {
if (theNextSibling.root == nullptr)
throw( InvalidTreeArgument() );
TreeNode<Object> *child = new TreeNode<Object>( theNextSibling.root->getElement(),
theNextSibling.root->getFirstChild(),
theNextSibling.root->getNextSibling() );
root->setNextSibling( child );
if (child != theNextSibling.root)
theNextSibling.root = nullptr;
}
template <class Object>
void Tree<Object>::merge( const Object& rootElement,
Tree & firstChild,
Tree & nextSibling ) {
if ( firstChild.root == nextSibling.root && firstChild.root != nullptr ) {
std::cerr << "Cannot merge a tree with itself" << std::endl;
throw( InvalidTreeArgument() );
}
else {
NodePtr oldRoot = root;
root = new TreeNode<Object>( rootElement,
firstChild.root,
nextSibling.root );
if (this != &firstChild && this != &nextSibling)
makeEmpty( oldRoot );
if (this != &firstChild)
firstChild.root = nullptr;
if (this != &nextSibling)
nextSibling.root = nullptr;
}
}
// Deep copy of tree
template <class Object>
const Tree<Object>& Tree<Object>::operator =( const Tree<Object>& rhs ) {
if (this != &rhs) {
makeEmpty();
if (rhs.root != nullptr)
root = rhs.root->duplicate();
}
return( *this );
}
template <class Object>
const Object& Tree<Object>::find( const Object& item ) const throw (ValueNotFound) {
TreeNode<Object>* node = find( item, root );
if (node == nullptr)
throw( ValueNotFound() );
return( node->getElement() );
}
template <class Object>
TreeNode<Object>* Tree<Object>::find( const Object& item, TreeNode<Object>* node ) const {
TreeNode<Object>* match = nullptr;
if (node != nullptr && node->getElement() == item) {
match = node;
}
if (node != nullptr && match == nullptr && node->getFirstChild() != nullptr) {
match = find( item, node->getFirstChild() );
}
if (node != nullptr && match == nullptr && node->getNextSibling() != nullptr) {
match = find( item, node->getNextSibling() );
}
return( match );
}
template <class Object>
void Tree<Object>::printTree( std::ostream & outs ) const {
if (isEmpty())
outs << "Empty Tree";
else {
TreeNode<Object> * node = getRoot();
node->printTreeNode( outs );
}
outs << std::endl;
}
}
#endif
/////////////////////////////////////////////////////////////////////////////////////
TreeNode.cpp
#ifndef TREENODE_CPP
#define TREENODE_CPP
#include <iostream>
#include <cstddef>
#include "TreeNode.h"
namespace cs20 {
template <class Object>
TreeNode<Object>::TreeNode( const Object& theElement,
TreeNode<Object> * theFirstChild,
TreeNode<Object> * theNextSibling ) {
element = theElement;
firstChild = theFirstChild;
nextSibling = theNextSibling;
}
template <class Object>
int TreeNode<Object>::size( TreeNode<Object> * node ) {
if (node == nullptr )
return( 0 );
else
return( 1 + size( node->firstChild ) + size( node->nextSibling ) );
}
template <class Object>
int TreeNode<Object>::height( TreeNode<Object> * node ) {
if (node == nullptr )
return( -1 );
else
return( std::max( height( node->firstChild ) + 1, height( node->nextSibling ) ) );
}
template <class Object>
TreeNode<Object> * TreeNode<Object>::duplicate( ) const {
TreeNode<Object> * newNode = new TreeNode<Object>( element );
if (firstChild != nullptr) {
newNode->firstChild = firstChild->duplicate();
}
if (nextSibling != nullptr) {
newNode->nextSibling = nextSibling->duplicate();
}
return( newNode );
}
template <class Object>
void TreeNode<Object>::printTreeNode( std::ostream & outs ) const {
Object o = element;
outs << o << " ";
if (firstChild != nullptr)
firstChild->printTreeNode( outs );
else
outs << "FCnullptr ";
if (nextSibling != nullptr)
nextSibling->printTreeNode( outs );
else
outs << "NSnullptr ";
outs << std::endl;
}
template <class Object>
const Object& TreeNode<Object>::getElement() const {
return( element );
}
template <class Object>
TreeNode<Object>* TreeNode<Object>::getFirstChild() const {
return( firstChild );
}
template <class Object>
TreeNode<Object>* TreeNode<Object>::getNextSibling() const {
return( nextSibling );
}
template <class Object>
void TreeNode<Object>::setFirstChild( TreeNode<Object>* node ) {
firstChild = node;
}
template <class Object>
void TreeNode<Object>::setNextSibling( TreeNode<Object>* node ) {
nextSibling = node;
}
}
#endif
/////////////////////////////////////////////////////////////////////////////////////
LevelOrderIterator.cpp
#ifndef LEVELORDERITERATOR_CPP
#define LEVELORDERITERATOR_CPP
#include <iostream>
#include <cstddef>
#include "TreeIterator.h"
#include "LevelOrderIterator.h"
#include "Queue.h"
namespace cs20 {
template <class Object>
LevelOrderIterator<Object>::LevelOrderIterator( const Tree<Object> & theTree ) : TreeIterator<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->getNextSibling() != nullptr)
q.enqueue( this->current->getNextSibling() );
if (this->current->getFirstChild() != nullptr)
q.enqueue( this->current->getFirstChild() );
}
}
}
#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;
}
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
/////////////////////////////////////////////////////////////////////////////////////
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 "Tree.h"
#include "Tree.cpp"
#include "TreeIterator.h"
#include "TreeIterator.cpp"
#include "TreeNode.h"
#include "TreeNode.cpp"
using namespace std;
using namespace cs20;
enum CHOICE {MAKEEMPTY, ISEMPTY, SIZE, HEIGHT, QUIT, PRINT, PRINTNODE, LEVELORDER, SETROOT, SETFIRST, SETNEXT, GOTOROOT, GOFIRST, GONEXT };
CHOICE menu();
void printTree( const Tree<int>& t );
int main(int argc, char* argv[]) {
int value;
Tree<int> tree;
TreeNode<int> * node = nullptr;
TreeNode<int> * firstnode = nullptr;
TreeNode<int> * nextnode = 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=" << TreeNode<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=" << TreeNode<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 SETFIRST:
try {
cout << "Enter a value for node's firstchild: ";
cin >> value;
firstnode = new TreeNode<int>( value );
node->setFirstChild( firstnode );
} catch( InvalidTreeArgument ita ) {
cout << "InvalidTreeArgument caught!" << endl;
}
break;
case SETNEXT:
try {
cout << "Enter a value for node's nextsibling: ";
cin >> value;
nextnode = new TreeNode<int>( value );
node->setNextSibling( nextnode );
} catch( InvalidTreeArgument ita ) {
cout << "InvalidTreeArgument caught!" << endl;
}
break;
case SETROOT:
cout << "Enter root value: ";
cin >> value;
// not sure this is too clever...
tree = Tree<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 GOFIRST:
node = node->getFirstChild();
break;
case GONEXT:
node = node->getNextSibling();
break;
case QUIT:
break;
}
} while (choice != QUIT);
return( 0 );
}
void printTree( const Tree<int> & t ) {
t.printTree( cout );
}
CHOICE menu() {
char choice;
CHOICE result;
cout << "(M)akeEmpty (I)sEmpty (S)ize (H)eight setRoo(T) set(F)irstChild set(N)extSibling gotoroot(1) gofi(R)st gone(X)tsibling (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 'F':
case 'f':
result = SETFIRST;
break;
case 'N':
case 'n':
result = SETNEXT;
break;
case 'R':
case 'r':
result = GOFIRST;
break;
case 'X':
case 'x':
result = GONEXT;
break;
case '1':
result = GOTOROOT;
break;
}
return( result );
}
/////////////////////////////////////////////////////////////////////////////////////
Tree.h
#ifndef TREE_H
#define TREE_H
// Visual Studio .NET does not support declared exceptions...
#pragma warning( disable:4290 )
#include <iostream>
#include "TreeNode.h"
#include "ValueNotFound.h"
namespace cs20 {
template <class Object>
class TreeIterator;
template <class Object>
class Tree {
public:
Tree();
Tree( const Object& rootElement );
Tree( const Tree& rhs );
~Tree();
bool isEmpty() const;
void makeEmpty();
int size() const;
int height() const;
void merge( const Object& rootElement,
Tree& firstChild,
Tree& nextSibling );
void setFirstChild( Tree& theFirstChild );
TreeNode<Object> * getFirstChild( ) const;
void setNextSibling( Tree& theNextSibling );
TreeNode<Object> * getNextSibling( ) const;
const Object& find( const Object& item ) const throw (ValueNotFound);
const Tree& operator =( const Tree& rhs );
void printTree( std::ostream & outs ) const;
const Object & getElement() const;
TreeNode<Object> * getRoot( ) const;
private:
typedef TreeNode<Object>* NodePtr;
NodePtr root;
void makeEmpty( NodePtr &t );
TreeNode<Object>* find( const Object& item, TreeNode<Object>* node ) const;
friend class TreeIterator<Object>;
};
}
#endif
/////////////////////////////////////////////////////////////////////////////////////
TreeNode.h
#ifndef TREENODE_H
#define TREENODE_H
#include <iostream>
#include <cstddef>
namespace cs20 {
template <class Object>
class TreeNode {
public:
TreeNode( const Object& theElement = Object(),
TreeNode * theFirstChild = nullptr,
TreeNode * theNextSibling = nullptr);
TreeNode * duplicate() const;
static int size( TreeNode * t );
static int height( TreeNode * t );
// no references to a TreeNode are returned
// publicly by either Tree or TreeIterator
// these methods are only called by Tree and
// TreeIterator
const Object& getElement() const;
TreeNode* getFirstChild() const;
TreeNode* getNextSibling() const;
void setFirstChild( TreeNode* node );
void setNextSibling( TreeNode* node );
void printTreeNode( std::ostream & outs ) const;
private:
Object element;
TreeNode* firstChild;
TreeNode* nextSibling;
};
}
#endif
/////////////////////////////////////////////////////////////////////////////////////
TreeIterator.h
#ifndef TREEITERATOR_H
#define TREEITERATOR_H
#include <iostream>
#include "TreeNode.h"
#include "Tree.h"
#include "BadIterator.h"
namespace cs20 {
template <class Object>
class TreeIterator {
public:
TreeIterator( const Tree<Object>& theTree );
virtual ~TreeIterator();
bool isValid() const;
virtual void advance() = 0;
virtual void first() = 0;
const Object& retrieve() const;
protected:
const TreeNode<Object> * current;
const TreeNode<Object> * root;
};
}
#endif
/////////////////////////////////////////////////////////////////////////////////////
TreeIterator.cpp
#ifndef TREEITERATOR_CPP
#define TREEITERATOR_CPP
#include <iostream>
#include <cstddef>
#include "TreeIterator.h"
namespace cs20 {
template <class Object>
TreeIterator<Object>::TreeIterator( const Tree<Object> & theTree ) : root( theTree.root ) , current( nullptr ) {
// all assignments performed above
}
template <class Object>
TreeIterator<Object>::~TreeIterator() {
}
template <class Object>
bool TreeIterator<Object>::isValid( ) const {
return( (current != nullptr) );
}
template <class Object>
const Object& TreeIterator<Object>::retrieve( ) const {
if (!(isValid())) throw BadIterator();
return( current->getElement() );
}
}
#endif
/////////////////////////////////////////////////////////////////////////////////////
LevelOrderIterator.h
#ifndef LEVELORDERITERATOR_H
#define LEVELORDERITERATOR_H
#include <iostream>
#include "Tree.h"
#include "TreeIterator.h"
#include "Queue.h"
namespace cs20 {
template <class Object>
class LevelOrderIterator : public TreeIterator<Object> {
public:
LevelOrderIterator( const Tree<Object>& theTree );
virtual ~LevelOrderIterator();
void advance();
void first();
protected:
Queue<const TreeNode<Object> *> q;
};
}
#endif
/////////////////////////////////////////////////////////////////////////////////////
ValueNotFound.cpp
#include "ValueNotFound.h"
namespace cs20 {
ValueNotFound::ValueNotFound( const std::string& msg ) : std::logic_error( msg.c_str() ) {}
}
/////////////////////////////////////////////////////////////////////////////////////
InvalidTreeArgument.cpp
#include "InvalidTreeArgument.h"
namespace cs20 {
InvalidTreeArgument::InvalidTreeArgument( const std::string& msg ) : std::logic_error( msg.c_str() ) {}
}
/////////////////////////////////////////////////////////////////////////////////////
BadIterator.cpp
#include "InvalidTreeArgument.h"
namespace cs20 {
InvalidTreeArgument::InvalidTreeArgument( 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
/////////////////////////////////////////////////////////////////////////////////////
ValueNotFound.h
#ifndef VALUENOTFOUND_H
#define VALUENOTFOUND_H
#include <iostream>
#include <string>
namespace cs20 {
class ValueNotFound : public std::logic_error {
public:
ValueNotFound( 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
Explanation / Answer
#ifndef TREE_CPP
#define TREE_CPP
#include <iostream>
#include <cstddef>
#include "Tree.h"
#include "TreeNode.h"
#include "InvalidTreeArgument.h"
namespace cs20 {
template <class Object>
Tree<Object>::Tree() {
root = nullptr;
}
template <class Object>
Tree<Object>::Tree( const Tree<Object>& rhs ) {
root = nullptr;
*this = rhs;
}
template <class Object>
Tree<Object>::Tree( const Object& rootElement ) {
root = new TreeNode<Object>( rootElement );
}
template <class Object>
Tree<Object>::~Tree() {
makeEmpty();
}
template <class Object>
const Object & Tree<Object>::getElement() const {
return( root->getElement() );
}
template <class Object>
bool Tree<Object>::isEmpty() const {
return( root == nullptr );
}
template <class Object>
void Tree<Object>::makeEmpty() {
makeEmpty( root );
}
template <class Object>
TreeNode<Object> * Tree<Object>::getFirstChild( ) const {
return( root->getFirstChild() );
}
template <class Object>
TreeNode<Object> * Tree<Object>::getNextSibling( ) const {
return( root->getNextSibling() );
}
template <class Object>
TreeNode<Object> * Tree<Object>::getRoot( ) const {
return( root );
}
template <class Object>
void Tree<Object>::makeEmpty( NodePtr & node ) {
if (node != nullptr) {
NodePtr fc = node->getFirstChild();
NodePtr ns = node->getNextSibling();
if (fc != nullptr)
makeEmpty( fc );
if (ns != nullptr)
makeEmpty( ns );
delete node;
node = nullptr;
}
}
template <class Object>
int Tree<Object>::size() const {
return( TreeNode<Object>::size( root ) );
}
template <class Object>
int Tree<Object>::height() const {
return( TreeNode<Object>::height( root ) );
}
template <class Object>
void Tree<Object>::setFirstChild( Tree& theFirstChild ) {
if (theFirstChild.root == nullptr)
throw( InvalidTreeArgument() );
TreeNode<Object> *child = new TreeNode<Object>( theFirstChild.root->getElement(),
theFirstChild.root->getFirstChild(),
theFirstChild.root->getNextSibling() );
root->setFirstChild( child );
if (child != theFirstChild.root)
theFirstChild.root = nullptr;
}
template <class Object>
void Tree<Object>::setNextSibling( Tree& theNextSibling ) {
if (theNextSibling.root == nullptr)
throw( InvalidTreeArgument() );
TreeNode<Object> *child = new TreeNode<Object>( theNextSibling.root->getElement(),
theNextSibling.root->getFirstChild(),
theNextSibling.root->getNextSibling() );
root->setNextSibling( child );
if (child != theNextSibling.root)
theNextSibling.root = nullptr;
}
template <class Object>
void Tree<Object>::merge( const Object& rootElement,
Tree & firstChild,
Tree & nextSibling ) {
if ( firstChild.root == nextSibling.root && firstChild.root != nullptr ) {
std::cerr << "Cannot merge a tree with itself" << std::endl;
throw( InvalidTreeArgument() );
}
else {
NodePtr oldRoot = root;
root = new TreeNode<Object>( rootElement,
firstChild.root,
nextSibling.root );
if (this != &firstChild && this != &nextSibling)
makeEmpty( oldRoot );
if (this != &firstChild)
firstChild.root = nullptr;
if (this != &nextSibling)
nextSibling.root = nullptr;
}
}
// Deep copy of tree
template <class Object>
const Tree<Object>& Tree<Object>::operator =( const Tree<Object>& rhs ) {
if (this != &rhs) {
makeEmpty();
if (rhs.root != nullptr)
root = rhs.root->duplicate();
}
return( *this );
}
template <class Object>
const Object& Tree<Object>::find( const Object& item ) const throw (ValueNotFound) {
TreeNode<Object>* node = find( item, root );
if (node == nullptr)
throw( ValueNotFound() );
return( node->getElement() );
}
template <class Object>
TreeNode<Object>* Tree<Object>::find( const Object& item, TreeNode<Object>* node ) const {
TreeNode<Object>* match = nullptr;
if (node != nullptr && node->getElement() == item) {
match = node;
}
if (node != nullptr && match == nullptr && node->getFirstChild() != nullptr) {
match = find( item, node->getFirstChild() );
}
if (node != nullptr && match == nullptr && node->getNextSibling() != nullptr) {
match = find( item, node->getNextSibling() );
}
return( match );
}
template <class Object>
void Tree<Object>::printTree( std::ostream & outs ) const {
if (isEmpty())
outs << "Empty Tree";
else {
TreeNode<Object> * node = getRoot();
node->printTreeNode( outs );
}
outs << std::endl;
}
}
#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 "Tree.h"
#include "Tree.cpp"
#include "TreeIterator.h"
#include "TreeIterator.cpp"
#include "TreeNode.h"
#include "TreeNode.cpp"
using namespace std;
using namespace cs20;
enum CHOICE {MAKEEMPTY, ISEMPTY, SIZE, HEIGHT, QUIT, PRINT, PRINTNODE, LEVELORDER, SETROOT, SETFIRST, SETNEXT, GOTOROOT, GOFIRST, GONEXT };
CHOICE menu();
void printTree( const Tree<int>& t );
int main(int argc, char* argv[]) {
int value;
Tree<int> tree;
TreeNode<int> * node = nullptr;
TreeNode<int> * firstnode = nullptr;
TreeNode<int> * nextnode = 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=" << TreeNode<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=" << TreeNode<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 SETFIRST:
try {
cout << "Enter a value for node's firstchild: ";
cin >> value;
firstnode = new TreeNode<int>( value );
node->setFirstChild( firstnode );
} catch( InvalidTreeArgument ita ) {
cout << "InvalidTreeArgument caught!" << endl;
}
break;
case SETNEXT:
try {
cout << "Enter a value for node's nextsibling: ";
cin >> value;
nextnode = new TreeNode<int>( value );
node->setNextSibling( nextnode );
} catch( InvalidTreeArgument ita ) {
cout << "InvalidTreeArgument caught!" << endl;
}
break;
case SETROOT:
cout << "Enter root value: ";
cin >> value;
// not sure this is too clever...
tree = Tree<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 GOFIRST:
node = node->getFirstChild();
break;
case GONEXT:
node = node->getNextSibling();
break;
case QUIT:
break;
}
} while (choice != QUIT);
return( 0 );
}
void printTree( const Tree<int> & t ) {
t.printTree( cout );
}
CHOICE menu() {
char choice;
CHOICE result;
cout << "(M)akeEmpty (I)sEmpty (S)ize (H)eight setRoo(T) set(F)irstChild set(N)extSibling gotoroot(1) gofi(R)st gone(X)tsibling (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 'F':
case 'f':
result = SETFIRST;
break;
case 'N':
case 'n':
result = SETNEXT;
break;
case 'R':
case 'r':
result = GOFIRST;
break;
case 'X':
case 'x':
result = GONEXT;
break;
case '1':
result = GOTOROOT;
break;
}
return( result );
}
/////////////////////////////////////////////////////////////////////////////////////
Tree.h
#ifndef TREE_H
#define TREE_H
// Visual Studio .NET does not support declared exceptions...
#pragma warning( disable:4290 )
#include <iostream>
#include "TreeNode.h"
#include "ValueNotFound.h"
namespace cs20 {
template <class Object>
class TreeIterator;
template <class Object>
class Tree {
public:
Tree();
Tree( const Object& rootElement );
Tree( const Tree& rhs );
~Tree();
bool isEmpty() const;
void makeEmpty();
int size() const;
int height() const;
void merge( const Object& rootElement,
Tree& firstChild,
Tree& nextSibling );
void setFirstChild( Tree& theFirstChild );
TreeNode<Object> * getFirstChild( ) const;
void setNextSibling( Tree& theNextSibling );
TreeNode<Object> * getNextSibling( ) const;
const Object& find( const Object& item ) const throw (ValueNotFound);
const Tree& operator =( const Tree& rhs );
void printTree( std::ostream & outs ) const;
const Object & getElement() const;
TreeNode<Object> * getRoot( ) const;
private:
typedef TreeNode<Object>* NodePtr;
NodePtr root;
void makeEmpty( NodePtr &t );
TreeNode<Object>* find( const Object& item, TreeNode<Object>* node ) const;
friend class TreeIterator<Object>;
};
}
#endif
/////////////////////////////////////////////////////////////////////////////////////
TreeNode.h
#ifndef TREENODE_H
#define TREENODE_H
#include <iostream>
#include <cstddef>
namespace cs20 {
template <class Object>
class TreeNode {
public:
TreeNode( const Object& theElement = Object(),
TreeNode * theFirstChild = nullptr,
TreeNode * theNextSibling = nullptr);
TreeNode * duplicate() const;
static int size( TreeNode * t );
static int height( TreeNode * t );
// no references to a TreeNode are returned
// publicly by either Tree or TreeIterator
// these methods are only called by Tree and
// TreeIterator
const Object& getElement() const;
TreeNode* getFirstChild() const;
TreeNode* getNextSibling() const;
void setFirstChild( TreeNode* node );
void setNextSibling( TreeNode* node );
void printTreeNode( std::ostream & outs ) const;
private:
Object element;
TreeNode* firstChild;
TreeNode* nextSibling;
};
}
#endif
/////////////////////////////////////////////////////////////////////////////////////
TreeIterator.h
#ifndef TREEITERATOR_H
#define TREEITERATOR_H
#include <iostream>
#include "TreeNode.h"
#include "Tree.h"
#include "BadIterator.h"
namespace cs20 {
template <class Object>
class TreeIterator {
public:
TreeIterator( const Tree<Object>& theTree );
virtual ~TreeIterator();
bool isValid() const;
virtual void advance() = 0;
virtual void first() = 0;
const Object& retrieve() const;
protected:
const TreeNode<Object> * current;
const TreeNode<Object> * root;
};
}
#endif
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.