C++ program Using the linked approach implement the BST ADT, implement only the
ID: 3738700 • Letter: C
Question
C++ program
Using the linked approach implement the BST ADT, implement only the following functions in the BSTree.cpp:
- constructor, copy constructor, assignment operator, destructor
- insert, retrieve, remove, writeKeys
- clear, isEmpty
Note: Use recursive functions to traverse the tree.
Config.h
* 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
#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
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"
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 << " ";
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
}
}
test9.cpp
#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;
}
Explanation / Answer
main.cpp
#include <iostream>
using namespace std;
#include "BSTree.cpp"
#include "config.h"
void print_help();
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,int> 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 << " <key : Write keys that are < key "
#if LAB9_TEST3
<< "(Active : "
#else
<< "(Inactive : "
#endif
<< "In-lab Exercise 3)" << endl;
cout << " Q : Quit the test program" << endl;
cout << endl;
}
BSTree.h
#ifndef BSTREE_H
#define BSTREE_H
#include <stdexcept>
#include <iostream>
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<DataType,KeyType>& other ); // Copy constructor
BSTree& operator= ( const BSTree<DataType,KeyType>& 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
};
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<DataType,KeyType> &otherTree );
void copyTreeHelper ( BSTreeNode *&p, const BSTreeNode *otherPtr );
// Data member
BSTreeNode *root; // Pointer to the root node
};
#endif // define BSTREE_H
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 1 // Programming Exercise 2: getCount
#define LAB9_TEST2 1 // Programming Exercise 2: getHeight
#define LAB9_TEST3 1 // Programming Exercise 3: writeLessThan
binaryTree.cpp
#include "BSTree.h"
#include <algorithm>
template <typename DataType, class KeyType>
void BSTree<DataType, KeyType>::copyTree(const BSTree<DataType, KeyType> &otherTree)
{
copyTreeHelper(root, otherTree.root);
}
template <typename DataType, class KeyType>
void BSTree<DataType, KeyType>::copyTreeHelper(BSTreeNode *&p, const BSTreeNode *otherPtr)
{
if (p != 0)
{
p = new BSTreeNode(otherPtr->dataItem, 0, 0);
copyTreeHelper(p->left, otherPtr->left)
copyTreeHelper(p->right, otherPtr->right);
}
}
template <typename DataType, class KeyType>
BSTree<DataType, KeyType>::BSTreeNode::BSTreeNode ( const DataType &nodeDataItem, BSTreeNode *leftPtr, BSTreeNode *rightPtr )
{
dataItem = nodeDataItem;
left = leftPtr;
right = rightPtr;
}
template < typename DataType, class KeyType >
BSTree<DataType, KeyType>::BSTree ()
{
root = NULL;
}
template < typename DataType, class KeyType >
BSTree<DataType, KeyType>::BSTree ( const BSTree<DataType,KeyType>& other )
{
*this = other;
}
template < typename DataType, class KeyType >
BSTree<DataType, KeyType>& BSTree<DataType, KeyType>:: operator= ( const BSTree<DataType,KeyType>& other )
{
if (*this == &other)
return *this;
clear();
copyTreeHelper(root, other.root);
return *this;
}
template < typename DataType, class KeyType >
BSTree<DataType, KeyType>::~BSTree ()
{
clearHelper(root);
}
template <typename DataType, class KeyType>
void BSTree<DataType, KeyType>::clearHelper(BSTreeNode * &p)
{
if (p != nullptr)
{
clearHelper(p->left);
clearHelper(p->right);
delete p;
}
p = nullptr;
}
template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::insert ( const DataType& newDataItem )
{
insertHelper(root, newDataItem);
}
template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::insertHelper(BSTreeNode *&p, const DataType &newDataItem)
{
if (p == nullptr)
p = new BSTreeNode{ newDataItem, nullptr, nullptr };
else if (newDataItem.getKey() < p->dataItem.getKey())
{
insertHelper(p->left,newDataItem);
}
else if (newDataItem.getKey() > p->dataItem.getKey())
{
insertHelper(p->right,newDataItem);
}
else; //duplicate, do nothing
}
template < typename DataType, class KeyType >
bool BSTree<DataType, KeyType>::retrieve ( const KeyType& searchKey, DataType& searchDataItem ) const
{
return retrieveHelper(root,searchKey, searchDataItem);
}
template < typename DataType, class KeyType >
bool BSTree<DataType, KeyType>::retrieveHelper(BSTreeNode *p, const KeyType& searchKey, DataType &searchDataItem) const
{
if (p == nullptr)
return false;
else if (searchKey < p->dataItem.getKey())
return retrieveHelper(p->left, searchKey, searchDataItem);
else if (searchKey > p->dataItem.getKey())
return retrieveHelper(p->right, searchKey, searchDataItem);
else
{
searchDataItem = p->dataItem;
return true; //match
}
}
template < typename DataType, class KeyType >
bool BSTree<DataType, KeyType>::remove ( const KeyType& deleteKey )
{
return removeHelper(root, deleteKey);
}
template < typename DataType, class KeyType >
bool BSTree<DataType, KeyType>::removeHelper(BSTreeNode *&p, const KeyType& deleteKey)
{
if (p == nullptr)
return false;
else if (deleteKey < p->dataItem.getKey())
{
return removeHelper(p->left, deleteKey);
}
else if (deleteKey > p->dataItem.getKey())
{
return removeHelper(p->right, deleteKey);
}
else{
BSTreeNode *oldNode = p;
if (p->left == nullptr)
p = p->right;
else if (p->right == nullptr)
p = p->left;
else
cutRightmost(p->left, oldNode);
delete oldNode;
return true;
}
}
template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::cutRightmost(BSTreeNode *&r, BSTreeNode *&delPtr)
{
if (r->right != nullptr)
cutRightmost(r->right, delPtr);
else
{
delPtr->dataItem = r->dataItem;
delPtr = r;
r = r->left;
}
}
template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::writeKeys () const
{
writeKeysHelper(root);
}
template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::writeKeysHelper(BSTreeNode *p) const
{
if (p != nullptr)
{
writeKeysHelper(p->left);
cout << p->dataItem.getKey() << " "; //line separated by spaces
writeKeysHelper(p->right);
}
return;
}
template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::clear ()
{
clearHelper(root);
}
template < typename DataType, class KeyType >
bool BSTree<DataType, KeyType>::isEmpty () const
{
return (root == nullptr);
}
template < typename DataType, class KeyType >
int BSTree<DataType, KeyType>::getHeight () const
{
return getHeightHelper(root);
}
template < typename DataType, class KeyType >
int BSTree<DataType, KeyType>::getHeightHelper(BSTreeNode *p) const
{
if (p != nullptr)
{
return max(getHeightHelper(p->left), getHeightHelper(p->right)) + 1;
}
else
return 0;
}
template < typename DataType, class KeyType >
int BSTree<DataType, KeyType>::getCount () const
{
return getCountHelper(root);
}
template < typename DataType, class KeyType >
int BSTree<DataType, KeyType>::getCountHelper(BSTreeNode *p) const
{
if (p == nullptr)
return 0;
else
return 1 + getCountHelper(p->left) + getCountHelper(p->right);
}
template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::writeLessThan ( const KeyType& searchKey ) const
{
writeLTHelper(root, searchKey);
}
template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::writeLTHelper(BSTreeNode *p, const KeyType& searchKey) const
{
if (p == nullptr)
return;
writeLTHelper(p->left, searchKey);
if (p->dataItem.getKey() < searchKey)
{
cout << p->dataItem.getKey() << " ";
writeLTHelper(p->right, searchKey);
}
}
#include "show9.cpp"
show9.cpp
#include "BSTree.h"
//--------------------------------------------------------------------
template < typename DataType, typename KeyType >
void BSTree<DataType,KeyType>:: showStructure () const
{
if ( root == 0 )
cout << "Empty tree" << endl;
else
{
cout << endl;
showHelper(root,1);
cout << endl;
}
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template < typename DataType, typename KeyType >
void BSTree<DataType,KeyType>:: showHelper ( BSTreeNode *p,
int level ) const
{
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 << " ";
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
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.