/***************************************************
bst.h
Author: David Pruitt
Information:
A Binary-Search-Tree class, originally created
for the Collections project in CS 240.
THIS CLASS HAS BEEN MODIFIED. Some small
modifications have been made to the class
in order to correctly implement it in the
"Make Project."
Change Log:
Here is a log of changes made. The "Make Project"
was made much more simple by use of key-value maps.
In order to have a key-value map, we first need
a set. It can be either a hash set or a tree set.
A Binary-Search-Tree is a tree set. No duplicate
values are allowed, thus defining it as a set. With
this in mind, I decided to use the binary search tree
as the back-bone code for the MAP_DTP class, or
the class that handles key-value maps in my "Make
Project."
In order to correctly implement the BST class as a
Tree Map suitable for key-value maps, a small change
had to be made to the BSTNode class, allowing it to
hold two pieces of information instread of one: a key,
and a value.
The variable names in the BSTNode class can be misleading.
In order to not have to make extensive modifications
throughout the code, I kept all original variables
the same, and simply added one variable called "kvalue",
which is the value mapped to by the key.
The misleading variable "value" is actually the key itself.
***************************************************/
#ifndef CS240_BST_H
#define CS240_BST_H
#include
using namespace std;
/*
BSTNode implements a binary search tree node
*/
class BSTNode {
friend class BST; // BST can access private members of BSTNode
friend class MAP_DTP;
private:
string value; // the node's KEY value
string kvalue; // the value mapped to by the KEY
BSTNode * left; // pointer to the node's left child
BSTNode * right; // pointer to the node's right child
int myid;
BSTNode ( ) : value(""), left(0), right(0)
{
}
public:
/*
Constructor
*/
BSTNode(const string & v) :
value(v), kvalue(""), left(0), right(0) {
return;
}
BSTNode ( const string & key, const string & val ) :
value(key), kvalue(val), left(0), right(0)
{
return;
}
/*
Read-only public methods for use by clients of the BST class
*/
//returns the key in the node
const string & GetValue() {
return value;
}
//returns the value mapped to by the key
const string & GetKValue ( ) {
return kvalue;
}
BSTNode * GetLeft() {
return left;
}
BSTNode * GetRight() {
return right;
}
};
/*
BST implements a binary search tree
*/
class BST {
friend class MAP_DTP;
protected:
BSTNode *Root;
int Size;
bool NodeRemoved;
void Free ( BSTNode * &root );
void Copy ( const BST & other );
BSTNode *CopyDown ( BSTNode *localRoot, BSTNode *otherRoot );
BSTNode *AddNode ( const string &v, BSTNode * &t );
BSTNode *Remove ( const string &x, BSTNode *t );
BSTNode *FindMin ( BSTNode *t );
BSTNode *RemoveMin ( BSTNode *n );
public:
/*
No-arg constructor. Initializes an empty BST
*/
BST();
/*
Copy constructor. Makes a complete copy of its argument
*/
BST(const BST & other);
/*
Destructor
*/
~BST();
/*
Assignment operator. Makes a complete copy of its argument
*/
void operator =(const BST & other);
/*
Returns a pointer to the root node of the tree, or 0 if the tree is empty.
(This is useful for BST clients that need to traverse the tree.)
*/
BSTNode * GetRoot() const;
/*
Returns true if the BST is empty, or false if the BST is not empty
*/
bool IsEmpty() const;
/*
Removes all values from the BST
*/
void Clear();
/*
Returns the number of values in the BST
*/
int GetSize() const;
/*
Inserts value v into the BST
Parameters:
v - The new value being inserted
Returns a pointer to the newly inserted node, or 0 if v was already
in the tree (i.e., 0 is used to indicate a duplicate insertion)
*/
BSTNode * Insert(const string & v);
/*
Searches the tree for value v
Parameters:
v - The new value being searched for
Returns a pointer to the node containing v, or 0 if v is not in the tree
*/
BSTNode * Find(const string & v) const;
/*
Removes value v from the tree
Parameters:
v - The value being removed from the tree
Returns true if v was removed from the tree, or false if v was not in the tree
*/
bool Remove(const string & v);
};
#endif