the implementation of the cs20::BinaryTree data structure presented in

the implementation of the cs20::BinaryTree< Object > data structure presented in

ID: 3846891 • Letter: T

Question

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:

template <class Object>
bool BinaryTree<Object>::cluster( Object o ) const throw( InvalidTreeArgument );

This method should determine if the tree has a cluster of Object o values. A cluster is when a node and both its immediate children have the same value. If the root of this BinaryTree is NULL, your code should throw an InvalidTreeArgument exception. 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.

For example, please consider the tree show below:

cluster( 7 ) on this tree should return false because there are no nodes with the element value of seven.

However, when working with the following tree:

cluster( 5 ) on this tree should return true because the red-colored nodes are a cluster, all with the element value of five.

files are provided in the link below

https://dropfile.to/Upapa4F access key: ewjhCpM

https://dropfile.to/pYHvNwr access key: xm4A6rH

4 12 10 8

Explanation / Answer

Added the needed code . The files updated are BinaryTree.h and BinaryTree.cpp. Also updated the driver file TreeMenu.cpp to test the new function. Here are the updated files and output. Please don't forget to rate the answer if it helped. Thank you very much.

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;

bool cluster(Object o) const;

private:

typedef BinaryTreeNode<Object>* NodePtr;

NodePtr root;

void makeEmpty( NodePtr &t );

friend class BinaryTreeIterator<Object>;

void printTree( NodePtr subtree, std::ostream & out ) const;

bool cluster( NodePtr node, Object ob ) const;

};

}

#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 << " ";

}

template <class Object>

bool BinaryTree<Object>::cluster( Object ob ) const

{

//throw an exception if root is null

if(root == nullptr)

throw( InvalidTreeArgument() );

return cluster(root, ob);

}

template <class Object>

bool BinaryTree<Object>::cluster( NodePtr node, Object ob ) const

{

bool match ;

if(node == nullptr)

return false;

//check if the node and both its childrent match the value of ob

match = (node->getElement() == ob);

match = match && node->getLeftSide() !=nullptr && node->getLeftSide()->getElement() == ob;

match = match && node->getRightSide() !=nullptr && node->getRightSide()->getElement() == ob;

if(match)

return true;

else

{

//if there was no match with node and its children, then check the left subtree and right subtree

return cluster(node->getLeftSide(), ob) || cluster(node->getRightSide(), ob);

}

#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, CLUSTER };

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 CLUSTER:

try {

cout << "Enter a value to search: ";

cin >> value;

if(tree.cluster(value))

cout << "tree has cluster with value " << value << endl;

else

cout << "tree does not have a cluster with the value " << value << endl;

} catch( InvalidTreeArgument ita ) {

cout << "InvalidTreeArgument 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 (C)luster (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 'C':

case 'c':

result = CLUSTER;

break;

case '1':

result = GOTOROOT;

break;

}

return( result );

}

output