Please Finish BSTree.cpp in C++, here are all the codes that came with it as well.

BSTree.cpp

#include "BSTree.h"

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

template BSTree::BSTree () { root = 0; }

template BSTree::BSTree ( const BSTree& other ) { }

template void BSTree:: copyTree(const BSTree &otherTree) { copyTreeHelper(root, otherTree.root); }

template void BSTree:: 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 BSTree& BSTree:: operator= ( const BSTree& other ) {

}

template BSTree::~BSTree () {

}

template void BSTree::insert ( const DataType& newDataItem ) {

}

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

template bool BSTree::remove ( const KeyType& deleteKey ) { return false; }

template bool BSTree::removeHelper(BSTreeNode *&p, const KeyType& deleteKey) {

}

template void BSTree::writeKeys () const {

}

template void BSTree::writeLTHelper(BSTreeNode *p, const KeyType& searchKey) const {

}

template void BSTree::clear () {

}

template void BSTree::clearHelper(BSTreeNode *p) {

}

template bool BSTree::isEmpty () const { return false; }

template int BSTree::getHeight () const { return -1; }

template int BSTree::getHeightHelper(BSTreeNode *p) const {

}

template int BSTree::getCount () const { return -1; }

template int BSTree::getCountHelper(BSTreeNode *p) const {

}

template void BSTree::writeLessThan ( const KeyType& searchKey ) const { }

#include "show9.cpp"

template

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

{

return false;

}

template

bool BSTree::remove ( const KeyType& deleteKey )

{

return false;

}

template

void BSTree::writeKeys () const

{

}

template

void BSTree::clear ()

{

}

template

bool BSTree::isEmpty () const

{

return false;

}

template

int BSTree::getHeight () const

{

return -1;

}

template

int BSTree::getCount () const

{

return -1;

}

template

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

{

}

#include "show9.cpp"

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

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 // 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

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

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

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

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

database.cs

// Builds a binary search tree index for the account records in the

// text file accounts.dat.

#include

#include

#include "BSTree.cpp"

using namespace std;

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

//

// Declarations specifying the accounts database

//

const int nameLength = 11; // Maximum number of characters in

// a name

const long bytesPerRecord = 38; // Number of bytes used to store

// each record in the accounts

// database file

struct AccountRecord

{

int acctID; // Account identifier

char firstName[nameLength], // Name of account holder

lastName[nameLength];

double balance; // Account balance

};

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

//

// Declaration specifying the database index

//

struct IndexEntry

{

int acctID; // (Key) Account identifier

long recNum; // Record number

int key () const

{ return acctID; } // Return key field

};

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

void main ()

{

ifstream acctFile ("accounts.dat"); // Accounts database file

AccountRecord acctRec; // Account record

BSTree index; // Database index

IndexEntry entry; // Index entry

int searchID; // User input account ID

long recNum; // Record number

// Iterate through the database records. For each record, read the

// account ID and add the (account ID, record number) pair to the

// index.

// Output the account IDs in ascending order.

// Clear the status flags for the database file.

acctFile.clear();

// Read an account ID from the keyboard and output the

// corresponding record.

}

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

show9.cpp

// Builds a binary search tree index for the account records in the

// text file accounts.dat.

#include

#include

#include "BSTree.cpp"

using namespace std;

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

//

// Declarations specifying the accounts database

//

const int nameLength = 11; // Maximum number of characters in

// a name

const long bytesPerRecord = 38; // Number of bytes used to store

// each record in the accounts

// database file

struct AccountRecord

{

int acctID; // Account identifier

char firstName[nameLength], // Name of account holder

lastName[nameLength];

double balance; // Account balance

};

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

//

// Declaration specifying the database index

//

struct IndexEntry

{

int acctID; // (Key) Account identifier

long recNum; // Record number

int key () const

{ return acctID; } // Return key field

};

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

void main ()

{

ifstream acctFile ("accounts.dat"); // Accounts database file

AccountRecord acctRec; // Account record

BSTree index; // Database index

IndexEntry entry; // Index entry

int searchID; // User input account ID

long recNum; // Record number

// Iterate through the database records. For each record, read the

// account ID and add the (account ID, record number) pair to the

// index.

// Output the account IDs in ascending order.

// Clear the status flags for the database file.

acctFile.clear();

// Read an account ID from the keyboard and output the

// corresponding record.

}

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

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

cin >> cmd;

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

cmd == '-' || cmd == '

cin >> inputKey;

switch ( cmd )

{

case 'P' : case 'p' :

print_help();

break;

case '+' : // insert

testData.setKey(inputKey);

cout

testTree.insert(testData);

break;

case '?' : // retrieve

if ( testTree.retrieve(inputKey,testData) )

cout

else

cout

break;

case '-' : // remove

if ( testTree.remove(inputKey) )

cout

else

cout

break;

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

cout

testTree.writeKeys();

break;

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

cout

testTree.clear();

break;

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

if ( testTree.isEmpty() )

cout

else

cout

break;

#if LAB9_TEST1

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

cout

break;

#endif // LAB9_TEST1

#if LAB9_TEST2

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

cout

break;

#endif // LAB9_TEST2

#if LAB9_TEST3

case '

cout

testTree.writeLessThan(inputKey);

cout

break;

#endif // LAB9_TEST3

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

break;

default : // Invalid command

cout

}

}

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

if ( !cin ) {

cerr

}

return 0;

}

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

void print_help() {

cout

cout

cout

cout

cout

cout

cout

cout

cout

#if LAB9_TEST1

#else

#endif

cout

#if LAB9_TEST2

#else

#endif

cout

#if LAB9_TEST3

#else

#endif

cout

cout

}

To Do: using the linked approach, implement the BST ADT, implement all the functions in the BSTree.cpp. (100 points) - use recursive functions to traverse the tree - read the implementation notes on using helper functions To Do: using the linked approach, implement the BST ADT, implement all the functions in the BSTree.cpp. (100 points) - use recursive functions to traverse the tree - read the implementation notes on using helper functions