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
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 // 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 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 { } template < typename DataType, class KeyType > BSTree { root = NULL; } template < typename DataType, class KeyType > BSTree { } template < typename DataType, class KeyType > BSTree { } template < typename DataType, class KeyType > BSTree { } template < typename DataType, class KeyType > void BSTree { } template < typename DataType, class KeyType > bool BSTree { return false; } template < typename DataType, class KeyType > bool BSTree { return false; } template < typename DataType, class KeyType > void BSTree { } template < typename DataType, class KeyType > void BSTree { } template < typename DataType, class KeyType > bool BSTree { return false; } template < typename DataType, class KeyType > int BSTree { return -1; } template < typename DataType, class KeyType > int BSTree { return -1; } template < typename DataType, class KeyType > void BSTree { } #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 BSTree& operator= ( const BSTree // 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 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
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started