Question

Please use the linked approach implement the BST ADT, implement all the functions in the BSTree.cpp. Add the ouput of the implementation.

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

Please use C++ programming

//////////////////////////////////////////////////////////////

#include "BSTree.h"

template <typename DataType, class KeyType>
BSTree<DataType, KeyType>::BSTreeNode::BSTreeNode ( const DataType &nodeDataItem, BSTreeNode *leftPtr, BSTreeNode *rightPtr )
{
}

template < typename DataType, class KeyType >
BSTree<DataType, KeyType>::BSTree ()
{
   root = 0;
}

template < typename DataType, class KeyType >
BSTree<DataType, KeyType>::BSTree ( const BSTree<DataType,KeyType>& other )
{
}

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>& BSTree<DataType, KeyType>:: operator= ( const BSTree<DataType,KeyType>& other )
{

}

template < typename DataType, class KeyType >
BSTree<DataType, KeyType>::~BSTree ()
{

}

template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::insert ( const DataType& newDataItem )
{

}

template < typename DataType, class KeyType >
bool BSTree<DataType, KeyType>::retrieve ( const KeyType& searchKey, DataType& searchDataItem ) const
{
   return false;
}

template < typename DataType, class KeyType >
bool BSTree<DataType, KeyType>::remove ( const KeyType& deleteKey )
{
   return false;
}

template < typename DataType, class KeyType >
bool BSTree<DataType, KeyType>::removeHelper(BSTreeNode *&p, const KeyType& deleteKey)
{

}

template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::writeKeys () const
{

}

template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::writeLTHelper(BSTreeNode *p, const KeyType& searchKey) const
{

}

template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::clear ()
{

}

template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::clearHelper(BSTreeNode *p)
{

}

template < typename DataType, class KeyType >
bool BSTree<DataType, KeyType>::isEmpty () const
{
   return false;
}

template < typename DataType, class KeyType >
int BSTree<DataType, KeyType>::getHeight () const
{
   return -1;
}

template < typename DataType, class KeyType >
int BSTree<DataType, KeyType>::getHeightHelper(BSTreeNode *p) const
{

}

template < typename DataType, class KeyType >
int BSTree<DataType, KeyType>::getCount () const
{
   return -1;
}

template < typename DataType, class KeyType >
int BSTree<DataType, KeyType>::getCountHelper(BSTreeNode *p) const
{

}

template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::writeLessThan ( const KeyType& searchKey ) const
{
}

#include "show9.cpp"

/////////////////////////////////////////////////////////////////////////////////////////

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 <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
   };

   // 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<DataType, KeyType> &otherTree);
   void copyTreeHelper(BSTreeNode *&p, const BSTreeNode *otherPtr);

   // Data member
   BSTreeNode *root; // Pointer to the root node
};

#endif   // define BSTREE_H

This is what the ouput is suppose to look like

//////////////////////////////////////////////////////////////////

Enpty tree Command: P Commands P Print Help +key Insert data key Retrieve data key Remove data Write keys in asc order Clear tree Empty tree? Get count of nodes KActive Tester 1 Height Active Tester 2 Kkey Write keys that are key KInactive Tester 3 Q quit the test progran Enpt y tree CAUsers1301595DocumentsWVisual Studio 2012MProjectsMBsTree Debug NBs Tree exe Command +1 Insert key 1 Command +2 Insert key 2 1/ Command +3 Insert key 3 Command: Not found 2/ 1/

Answer 1

Please find the code below:
If you have any problems here, will help you please let me know.

BSTree.cpp
#include "BSTree.h"

template <typename DataType, class KeyType>
BSTree<DataType, KeyType>::BSTree () { // Default constructor
root = NULL;
counter = 0;
   cursor = NULL;
}

template <typename DataType, class KeyType>
BSTree<DataType, KeyType>::BSTree ( const BSTree<DataType,KeyType>& other ) { // Copy constructor
   *this = other;
}

template <typename DataType, class KeyType>
BSTree<DataType, KeyType>& BSTree<DataType, KeyType>::operator= ( const BSTree<DataType,KeyType>& other ) {
   if (this != other) {
       clear();
       root = assignHelper(root);
   }   
   return *this;
}

template <typename DataType, class KeyType>
typename BSTree<DataType,KeyType>::BSTreeNode* BSTree<DataType, KeyType>::assignHelper(BSTreeNode* copy) {
   BSTreeNode* pointer;
   if (copy != NULL) {
       pointer = new BSTreeNode(copy.dataItem, copy->left, copy->right);
   }
   else {
       pointer = NULL;
   }
   return pointer;
}

// Destructor
template <typename DataType, class KeyType>
BSTree<DataType, KeyType>::~BSTree () {
clear();
root = NULL;   
counter = 0;
}

   //searches the tree
template <typename DataType, class KeyType>
char BSTree<DataType, KeyType>::search(KeyType data){
   char direction;
   if(data < cursor->dataItem.getKey() && cursor->left != NULL){
       cursor = cursor->left;
       direction = search(data);
   }
   else if(data > cursor->dataItem.getKey() && cursor->right !=NULL){
       cursor = cursor->right;
       direction = search(data);
   }
   else{
       if(data == cursor->dataItem.getKey())
           direction = 'n';
       else if(data < cursor->dataItem.getKey())
           direction = 'l';
       else if(data > cursor->dataItem.getKey())
           direction = 'r';
   }
   return direction;
}

// Binary search tree manipulation operations
template <typename DataType, class KeyType>
void BSTree<DataType, KeyType>::insert ( const DataType& newDataItem ) { // Insert data item
if (isEmpty()) {
root = new BSTreeNode(newDataItem, NULL, NULL);
counter++;
}
else {
//need to sort into correct node position within tree
   cursor = root;
   char direction = search( newDataItem.getKey());
   if(direction == 'l')
           cursor->left = new BSTreeNode(newDataItem, NULL, NULL);
   else if(direction == 'r')
           cursor->right = new BSTreeNode(newDataItem, NULL, NULL);
   else
           cout << "Cannot insert duplicates of the same item!\n\n";
counter++;
}
   cursor = root;
}

template <typename DataType, class KeyType> //Retrieve data item
bool BSTree<DataType, KeyType>::retrieve ( const KeyType& searchKey, DataType& searchDataItem ) {
   cursor = root;
   char direction = search(searchKey);
if (direction == 'n') {
       searchDataItem = cursor->dataItem;
       return true;
   }
   else {
       return false;
   }
}

//---------------------------------------------------------
template <typename DataType, class KeyType>
bool BSTree<DataType, KeyType>::remove ( const KeyType& deleteKey) { // Remove data item
if (isEmpty()) {
return false;
cout << "Tree is empty! Cannot remove." << endl;
}
/*else {
return removeHelper(deleteKey, root);
}*/
}

/*template <typename DataType, class KeyType>
bool BSTree<DataType, KeyType>::removeHelper(KeyType deleteKey, BSTreeNode* lostNode) {
if (lostNode == NULL) {
return;
}
if (deleteKey < lostNode->dataItem.getKey()) {
removeHelper(deleteKey, lostNode->left);   
return true;   
}
else if(lostNode->dataItem.getKey() < deleteKey) {
removeHelper(deleteKey, lostNode->right);
return true;   
}
else if (lostNode->left != NULL && lostNode->right != NULL) {
lostNode->dataItem = findMin(lostNode->right)->dataItem.getKey();
removeHelper(lostNode->dataItem, lostNode->right);   
return true;
}
else {
BSTreeNode *oldNode = lostNode;
lostNode = (lostNode->left != NULL) ? lostNode->left : lostNode->right;
delete oldNode;   
return true;
}
}*/

/*template <typename DataType, class KeyType>
typename BSTree<DataType,KeyType>::BSTreeNode* BSTree<DataType, KeyType>::findMin(BSTreeNode* node) {
if (node == NULL) {
return NULL;
}
if (node->left == NULL) {
return node;
}
return findMin(node->left);
}*/

template <typename DataType, class KeyType>
void BSTree<DataType, KeyType>::writeKeys () const { // Output keys
if (isEmpty()) {
cout << "Empty tree!" << endl;
}
else {
writeKeysHelper(root);
}
}

template <typename DataType, class KeyType>
void BSTree<DataType, KeyType>::writeKeysHelper(BSTreeNode *node) const {
if (node != NULL) {
writeKeysHelper(node->left);
cout << node->dataItem.getKey() << endl;
writeKeysHelper(node->right);
}
}

template <typename DataType, class KeyType>
void BSTree<DataType, KeyType>::clear () { // Clear tree
if (root == NULL && counter == 0) {
cout << "Tree is already empty!" << endl;
}
else {
helpClear(root);
root = NULL;
counter = 0;
}
}

template <typename DataType, class KeyType>
void BSTree<DataType, KeyType>::helpClear(BSTreeNode* gone) {
if (gone != NULL) {
helpClear(gone->left);
helpClear(gone->right);
delete gone;
}
gone = NULL;
counter = 0;
}

// Binary search tree status operations
template <typename DataType, class KeyType>
bool BSTree<DataType, KeyType>::isEmpty () const { // Tree is empty
// !! isFull() has been retired. Not very useful in a linked structure.
if (root == NULL && counter == 0) {
return true;
}
else {
return false;
}
}

// Output the tree structure -- used in testing/debugging
template < typename DataType, typename KeyType >
void BSTree<DataType,KeyType>:: 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;
}
}

// In-lab operations
template <typename DataType, class KeyType>
int BSTree<DataType, KeyType>::getHeight () { // Height of tree
int height;
if (isEmpty()) {
height = 0;
}
else {
height = heightHelper(root);
}
return height;
}

template <typename DataType, class KeyType>
int BSTree<DataType, KeyType>::heightHelper(BSTreeNode* heightNode) {
if (heightNode != NULL) {
return (max(heightHelper(heightNode->left), heightHelper(heightNode->right))+1);
}
   else {
       return 0;
   }
}

template <typename DataType, class KeyType>
int BSTree<DataType, KeyType>::getCount () const {           // Number of nodes in tree
return counter;
}

//---------------------------------------------------------------
template <typename DataType, class KeyType>
void BSTree<DataType, KeyType>::writeLessThan ( const KeyType& searchKey ) { // Output keys < searchKey
if (isEmpty()) {
cout << "Tree is empty!" << endl;
}
else {
writeLessHelper(root, searchKey);
}
}

//--------------------------------------------------------------------
template <typename DataType, class KeyType>
void BSTree<DataType, KeyType>::writeLessHelper(BSTreeNode* pointer, KeyType searchKey) {
if (pointer == NULL) {
return;
}
else {if (pointer->dataItem.getKey() >= searchKey) {
writeLessHelper(pointer->left, searchKey);
}
else {
pointer = pointer->left;
cout << pointer->dataItem.getKey() << endl;
writeLessHelper(pointer->right, searchKey);
}   
}
}
  
// Constructor
template <typename DataType, class KeyType>
BSTree<DataType, KeyType>::BSTreeNode::BSTreeNode( const DataType &nodeDataItem, BSTreeNode *leftPtr, BSTreeNode *rightPtr ) {
dataItem = nodeDataItem;
left = leftPtr;
right = rightPtr;   
}

// Recursive helpers for the public member functions -- insert
// prototypes of these functions here.
  
  
template <typename DataType, class KeyType>
void BSTree<DataType,KeyType>:: 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.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

//   BSTree& traverse();
//   void search(KeyType data, char& direction = 'l');

   char search(KeyType data);
   void insert ( const DataType& newDataItem ); // Insert data item
   //bool retrieve (KeyType searchKey, DataType& searchDataItem ) const;
bool retrieve ( const KeyType& searchKey, DataType& searchDataItem );
// 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 (); // Height of tree
int getCount () const;           // Number of nodes in tree
void writeLessThan ( const KeyType& searchKey ); // 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 showHelper ( BSTreeNode *p, int level ) const;
//BSTreeNode* findMin(BSTreeNode* node)const;
void writeKeysHelper(BSTreeNode *node) const;
    void helpClear(BSTreeNode* gone);  
int heightHelper(BSTreeNode* heightNode);
   typename BSTree<DataType, KeyType>::BSTreeNode* assignHelper(BSTreeNode* copy);
   void writeLessHelper(BSTreeNode* pointer, KeyType searchkey);
   //bool removeHelper(KeyType deleteKey, BSTreeNode* lostNode);
   //typename BSTree<DataType,KeyType>::BSTreeNode* findMin(BSTreeNode* node) {
  
   // Data member
   BSTreeNode *cursor;
BSTreeNode *root; // Pointer to the root node
int counter; //helper member
};

#endif   // define BSTREE_H

driver.cpp
using namespace std;

#include <iostream>
#include "BSTree.cpp"

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,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;

case 'G' : case 'g' :   
cout << "Tree nodes count = " << testTree.getCount() << endl;
break;

case 'H' : case 'h' :   
cout << "Tree height = " << testTree.getHeight() << endl;
break;

       case '<' :
cout << "Keys < " << inputKey << " : " << endl;
testTree.writeLessThan(inputKey);
cout << endl;
break;

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 (Active : Tester 1)" << endl;
   cout << " H : Height (Active : Tester 2) " << endl;
   cout << " Q : Quit the test program" << endl;
cout << endl;
}