The exercise will be marked out of 10, and is worth 5% of your total grade.
Late submissions will be penalized 2.5 marks per day late or part thereof.
Exercise details:
For lab exercise 4 you will be working with a binary search tree class (defined in BSTree.h)
You will be creating a file called BSTree.C, and in it you will implement the six protected binary search tree methods:
You will see that the public binary search tree methods have already been implemented inside BSTree.h, and each of them simply calls one of the protected methods that you are implementing.
The code below is available in files labex4.C, and BSTree.h
// BSTree.h
#ifndef BSTREE_H
#define BSTREE_H
#include <string>
using namespace std;
// ====================================================================
// ====== Binary search tree class ====================================
class BSTree {
protected:
// define the structure of internal tree nodes
struct tNode {
string key, value;
tNode *left, *right;
};
// root will point to the root node of the tree
tNode *root;
// return the size of a subtree rooted at t
int getSize(tNode *t);
// insert the key/value pair in the subtree t
bool insert(string key, string value, tNode* &t);
// lookup the key in the subtree t
bool lookup(string key, string &value, tNode *t);
// remove the specified item from subtree t
bool remove(string key, string &value, tNode* &t);
// print the contents of subtree t
void printSubtree(tNode *t);
// delete all nodes in the subtree t
void deleteSubtree(tNode* &t);
public:
// the public routines are simply implemented with
// inline calls to the internal protected routines
BSTree()
{ root = NULL; }
~BSTree()
{ deleteSubtree(root); }
int getSize()
{ return getSize(root); }
bool insert(string key, string value)
{ return insert(key, value, root); }
bool lookup(string key, string &value)
{ return lookup(key, value, root); }
bool remove(string key, string &value)
{ return remove(key, value, root); }
void printAll()
{ printSubtree(root); }
};
#endif
|
// labex4.C
#include "BSTree.h"
#include <iostream>
using namespace std;
// ====================================================================
// ====== Constants and data types ====================================
// enumerated type to list valid user commands
enum Command {
HelpCmd = 'H',
InsertCmd = 'I',
LookupCmd = 'L',
PrintCmd = 'P',
QuitCmd = 'Q',
RemoveCmd = 'R',
SizeCmd = 'S',
InvalidCmd = '-'
};
// constant to specify maximum length of a line of text
const int MaxTextLen = 256;
// ====================================================================
// ====== Function prototypes =========================================
string getKey();
string getValue();
Command getCommand();
void processCommand(Command cmd, BSTree* s);
void printCommands();
// ====================================================================
// ====== Main routine ================================================
int main()
{
// try creating a BSTree to store the data,
// exit if unsuccessful
BSTree *database = new BSTree;
if (!database) {
cout << "Exiting: unable to allocate storage" << endl;
return 0;
}
// process user commands, updating the tree,
// until the user decides to quit
printCommands();
Command cmd;
do {
cmd = getCommand();
processCommand(cmd, database);
} while (cmd != QuitCmd);
}
// ====================================================================
// ====== Function implementations ====================================
string getKey()
{
char text[MaxTextLen];
cout << "Enter the desired key value\n";
cin.getline(text, MaxTextLen);
string key = text;
return key;
}
string getValue()
{
char text[MaxTextLen];
cout << "Enter the desired data value\n";
cin.getline(text, MaxTextLen);
string value = text;
return value;
}
Command getCommand()
{
char cmd;
char junk[MaxTextLen];
do {
cout << "Enter a command" << endl;
cin >> cmd;
cin.getline(junk, MaxTextLen);
switch (toupper(cmd)) {
case HelpCmd: return HelpCmd;
case InsertCmd: return InsertCmd;
case LookupCmd: return LookupCmd;
case PrintCmd: return PrintCmd;
case QuitCmd: return QuitCmd;
case RemoveCmd: return RemoveCmd;
case SizeCmd: return SizeCmd;
default:
cout << "Invalid command entered: " << cmd;
cout << ", please try again" << endl;
cmd = InvalidCmd;
break;
}
} while (cmd == InvalidCmd);
return (Command)(cmd);
}
void printCommands()
{
cout << "Enter " << (char)(HelpCmd)
<< " for help" << endl;
cout << " or " << (char)(InsertCmd)
<< " to insert a new key/value pair" << endl;
cout << " or " << (char)(LookupCmd)
<< " to lookup the value associate with a key" << endl;
cout << " or " << (char)(PrintCmd)
<< " to print all the key/value pairs" << endl;
cout << " or " << (char)(RemoveCmd)
<< " to remove a key/value pair" << endl;
cout << " or " << (char)(SizeCmd)
<< " to lookup how many key/value pairs are stored" << endl;
cout << " or " << (char)(QuitCmd)
<< " to quit" << endl;
}
void processCommand(Command cmd, BSTree* s)
{
if (!s) {
cout << "Cannot process an uninitialized database" << endl;
return;
}
string key, value;
switch (cmd) {
case HelpCmd:
printCommands();
break;
case InsertCmd:
key = getKey();
value = getValue();
if (s->insert(key, value)) {
cout << "Inserted (" << key << "," << value << ")\n";
} else {
cout << "Unable to insert (" << key << "," << value << ")\n";
}
break;
case LookupCmd:
key = getKey();
if (s->lookup(key, value)) {
cout << "Looked up (" << key << "," << value << ")\n";
} else {
cout << "Unable to lookup (" << key << ")\n";
}
break;
case PrintCmd:
cout << "Current database contents:\n";
s->printAll();
break;
case QuitCmd:
cout << "Bye!\n";
break;
case RemoveCmd:
key = getKey();
if (s->remove(key, value)) {
cout << "Removed (" << key << "," << value << ")\n";
} else {
cout << "Unable to find (" << key << ") to remove\n";
}
break;
case SizeCmd:
cout << "There are " << s->getSize();
cout << " key/value pairs currently stored\n";
break;
default:
cout << "Invalid command supplied, please try again\n";
break;
}
}
|
Recommended development sequence As always, I advise you follow a well-thought out sequence of development steps in completing the exercise.
PHASE 0 setup the files
PHASE I insert and print
PHASE II searches
PHASE III the rest
PHASE IV testing
Submission mechanism
All the code for the BSTree methods must be in file BSTree.C
(correct spelling and capitalization
is essential for the submission to work correctly).
To submit the assignment, cd to the directory that contains your BSTree.C file and type the following command:
/home/faculty/wesselsd/bin/submit 161 BSTree.C
Marking guidelines:
Marks will be based on:
Code standards:
The submission must follow the code standards for labex3,