Answered step by step
Verified Expert Solution
Link Copied!
Question
1 Approved Answer

C++ Programming. Please only answer if you can do the ENTIRE problem. Make the files copyable with a screenshot of the output. All code is

C++ Programming. Please only answer if you can do the ENTIRE problem. Make the files copyable with a screenshot of the output. All code is listed below just complete the To Do parts. Really appreciate it, can't wait to give you a thumbs up for your work :-)

To Do:

- using the linked approach implement the BST ADT, implement all the functions in the BSTree.cpp. (60 points)

- use recursive functions to traverse the tree - read the implementation notes on using helper functions.

- Programming Exercise 2 (20 points)

- Programming Exercise 3 (20 points)

test9.cpp:

//--------------------------------------------------------------------

//

// Laboratory 9 test9.cpp

//

// Test program for the operations in the Binary Search Tree ADT

//

//--------------------------------------------------------------------

#include

using namespace std;

#include "BSTree.cpp"

#include "config.h"

void print_help();

//--------------------------------------------------------------------

// Declaration for the binary search tree data item class

//--------------------------------------------------------------------

class TestData

{

public:

void setKey ( int newKey )

{ keyField = newKey; } // Set the key

int getKey () const

{ return keyField; } // Returns the key

private:

int keyField; // Key for the data item

};

int main()

{

BSTree testTree; // Test binary search tree

TestData testData; // Binary search tree data item

int inputKey; // User input key

char cmd; // Input command

print_help();

do

{

testTree.showStructure(); // Output tree

cout << endl << "Command: "; // Read command

cin >> cmd;

if ( cmd == '+' || cmd == '?' ||

cmd == '-' || cmd == '<' )

cin >> inputKey;

switch ( cmd )

{

case 'P' : case 'p' :

print_help();

break;

case '+' : // insert

testData.setKey(inputKey);

cout << "Insert : key = " << testData.getKey()

<< endl;

testTree.insert(testData);

break;

case '?' : // retrieve

if ( testTree.retrieve(inputKey,testData) )

cout << "Retrieved : getKey = "

<< testData.getKey() << endl;

else

cout << "Not found" << endl;

break;

case '-' : // remove

if ( testTree.remove(inputKey) )

cout << "Removed data item" << endl;

else

cout << "Not found" << endl;

break;

case 'K' : case 'k' : // writeKeys

cout << "Keys:" << endl;

testTree.writeKeys();

break;

case 'C' : case 'c' : // clear

cout << "Clear the tree" << endl;

testTree.clear();

break;

case 'E' : case 'e' : // empty

if ( testTree.isEmpty() )

cout << "Tree is empty" << endl;

else

cout << "Tree is NOT empty" << endl;

break;

#if LAB9_TEST1

case 'G' : case 'g' : // Programming Exercise 2

cout << "Tree nodes count = " << testTree.getCount() << endl;

break;

#endif // LAB9_TEST1

#if LAB9_TEST2

case 'H' : case 'h' : // Programming Exercise 2

cout << "Tree height = " << testTree.getHeight() << endl;

break;

#endif // LAB9_TEST2

#if LAB9_TEST3

case '<' : // Programming Exercise 3

cout << "Keys < " << inputKey << " : " << endl;

testTree.writeLessThan(inputKey);

cout << endl;

break;

#endif // LAB9_TEST3

case 'Q' : case 'q' : // Quit test program

break;

default : // Invalid command

cout << "Inactive or invalid command. 'P' prints help." << endl;

}

}

while ( cin && ( cmd != 'Q' ) && ( cmd != 'q' ) );

if ( !cin ) {

cerr << "Error in console input. Exiting." << endl;

}

return 0;

}

//--------------------------------------------------------------------

void print_help() {

cout << endl << "Commands:" << endl;

cout << " P : [P]rint Help (displays this message)" << endl;

cout << " +key : Insert (or update) data item (use integers)" << endl;

cout << " ?key : Retrieve data item" << endl;

cout << " -key : Remove data item" << endl;

cout << " K : Write keys in ascending order" << endl;

cout << " C : Clear the tree" << endl;

cout << " E : Empty tree?" << endl;

cout << " G : Get count of nodes "

#if LAB9_TEST1

<< "(Active : "

#else

<< "(Inactive : "

#endif

<< "In-lab Exercise 2)" << endl;

cout << " H : Height "

#if LAB9_TEST2

<< "(Active : "

#else

<< "(Inactive : "

#endif

<< "In-lab Exercise 2)" << endl;

cout << "

#if LAB9_TEST3

<< "(Active : "

#else

<< "(Inactive : "

#endif

<< "In-lab Exercise 3)" << endl;

cout << " Q : Quit the test program" << endl;

cout << endl;

}

show9.cpp:

#include "BSTree.h"

//--------------------------------------------------------------------

//

// Laboratory 9 show9.cpp

//

// Linked implementation of the showStructure operation for the

// Binary Search Tree ADT

//

//--------------------------------------------------------------------

//--------------------------------------------------------------------

template < typename DataType, typename KeyType >

void BSTree:: showStructure () const

// Outputs the keys in a binary search tree. The tree is output

// rotated counterclockwise 90 degrees from its conventional

// orientation using a "reverse" inorder traversal. This operation is

// intended for testing and debugging purposes only.

{

if ( root == 0 )

cout << "Empty tree" << endl;

else

{

cout << endl;

showHelper(root,1);

cout << endl;

}

}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

template < typename DataType, typename KeyType >

void BSTree:: showHelper ( BSTreeNode *p,

int level ) const

// Recursive helper for showStructure.

// Outputs the subtree whose root node is pointed to by p.

// Parameter level is the level of this node within the tree.

{

int j; // Loop counter

if ( p != 0 )

{

showHelper(p->right,level+1); // Output right subtree

for ( j = 0 ; j < level ; j++ ) // Tab over to level

cout << "\t";

cout << " " << p->dataItem.getKey(); // Output key

if ( ( p->left != 0 ) && // Output "connector"

( p->right != 0 ) )

cout << "<";

else if ( p->right != 0 )

cout << "/";

else if ( p->left != 0 )

cout << "\\";

cout << endl;

showHelper(p->left,level+1); // Output left subtree

}

}

BSTree.cpp:

#include "BSTree.h"

template

BSTree::BSTreeNode::BSTreeNode ( const DataType &nodeDataItem, BSTreeNode *leftPtr, BSTreeNode *rightPtr )

{

}

template < typename DataType, class KeyType >

BSTree::BSTree ()

{

root = NULL;

}

template < typename DataType, class KeyType >

BSTree::BSTree ( const BSTree& other )

{

}

template < typename DataType, class KeyType >

BSTree& BSTree:: operator= ( const BSTree& other )

{

}

template < typename DataType, class KeyType >

BSTree::~BSTree ()

{

}

template < typename DataType, class KeyType >

void BSTree::insert ( const DataType& newDataItem )

{

}

template < typename DataType, class KeyType >

bool BSTree::retrieve ( const KeyType& searchKey, DataType& searchDataItem ) const

{

return false;

}

template < typename DataType, class KeyType >

bool BSTree::remove ( const KeyType& deleteKey )

{

return false;

}

template < typename DataType, class KeyType >

void BSTree::writeKeys () const

{

}

template < typename DataType, class KeyType >

void BSTree::clear ()

{

}

template < typename DataType, class KeyType >

bool BSTree::isEmpty () const

{

return false;

}

template < typename DataType, class KeyType >

int BSTree::getHeight () const

{

return -1;

}

template < typename DataType, class KeyType >

int BSTree::getCount () const

{

return -1;

}

template < typename DataType, class KeyType >

void BSTree::writeLessThan ( const KeyType& searchKey ) const

{

}

#include "show9.cpp"

config.h:

/**

* BSTree class (Lab 9) configuration file.

* Activate test 'N' by defining the corresponding LAB9_TESTN to have the value 1.

* Deactive test 'N' by setting the value to 0.

*/

#define LAB9_TEST1 0 // Programming Exercise 2: getCount

#define LAB9_TEST2 0 // Programming Exercise 2: getHeight

#define LAB9_TEST3 0 // Programming Exercise 3: writeLessThan

BSTree.h:

//--------------------------------------------------------------------

//

// Laboratory 9 BSTree.h

//

// Class declarations for the linked implementation of the Binary

// Search Tree ADT -- including the recursive helpers of the

// public member functions

//

//--------------------------------------------------------------------

#ifndef BSTREE_H

#define BSTREE_H

#include

#include

using namespace std;

template < typename DataType, class KeyType > // DataType : tree data item

class BSTree // KeyType : key field

{

public:

// Constructor

BSTree (); // Default constructor

BSTree ( const BSTree& other ); // Copy constructor

BSTree& operator= ( const BSTree& other );

// Overloaded assignment operator

// Destructor

~BSTree ();

// Binary search tree manipulation operations

void insert ( const DataType& newDataItem ); // Insert data item

bool retrieve ( const KeyType& searchKey, DataType& searchDataItem ) const;

// Retrieve data item

bool remove ( const KeyType& deleteKey ); // Remove data item

void writeKeys () const; // Output keys

void clear (); // Clear tree

// Binary search tree status operations

bool isEmpty () const; // Tree is empty

// !! isFull() has been retired. Not very useful in a linked structure.

// Output the tree structure -- used in testing/debugging

void showStructure () const;

// In-lab operations

int getHeight () const; // Height of tree

int getCount () const; // Number of nodes in tree

void writeLessThan ( const KeyType& searchKey ) const; // Output keys < searchKey

protected:

class BSTreeNode // Inner class: facilitator for the BSTree class

{

public:

// Constructor

BSTreeNode ( const DataType &nodeDataItem, BSTreeNode *leftPtr, BSTreeNode *rightPtr );

// Data members

DataType dataItem; // Binary search tree data item

BSTreeNode *left, // Pointer to the left child

*right; // Pointer to the right child

};

// Recursive helpers for the public member functions -- insert

// prototypes of these functions here.

void insertHelper ( BSTreeNode *&p, const DataType &newDataItem );

bool retrieveHelper ( BSTreeNode *p, const KeyType& searchKey, DataType &searchDataItem ) const;

bool removeHelper ( BSTreeNode *&p, const KeyType& deleteKey );

// cutRightmose used in one implementation of remove.

void cutRightmost ( BSTreeNode *&r, BSTreeNode *&delPtr );

void writeKeysHelper ( BSTreeNode *p ) const;

void clearHelper ( BSTreeNode *p );

void showHelper ( BSTreeNode *p, int level ) const;

int getHeightHelper ( BSTreeNode *p ) const;

int getCountHelper ( BSTreeNode *p ) const;

void writeLTHelper ( BSTreeNode *p, const KeyType& searchKey ) const;

void copyTree ( const BSTree &otherTree );

void copyTreeHelper ( BSTreeNode *&p, const BSTreeNode *otherPtr );

// Data member

BSTreeNode *root; // Pointer to the root node

};

#endif // define BSTREE_H

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image
Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image_2

Step: 3

blur-text-image_3

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Inductive Databases And Constraint Based Data Mining

Authors: Saso Dzeroski ,Bart Goethals ,Pance Panov

2010th Edition

1489982175, 978-1489982179

More Books

Students explore these related Databases questions