NEED HELP! BST!

[Sayraa87]

I am working on getting this to run correctly. I am making a BST trying to get it to have pointers to the left and right and parent. I think I have been looking at it too long to catch any mistakes right now. Any help will be greatly appriciated!

#include "StdAfx.h"
#include "BinaryTreeMap.h"
#include <iostream>

BinaryTreeMap::BinaryTreeMap(void)
{
versionNumber=1;
n=0;
root = new Node(NULL);
}

BinaryTreeMap::~BinaryTreeMap(void)
{

deleteSubtree(root);
}

int BinaryTreeMap::size() const
{
return n;
}

bool BinaryTreeMap::empty() const
{
return n==0;
}

BinaryTreeMap::iterator BinaryTreeMap::find(const MapKey& k)
{
Node* myNode = binarySearchTreeFind(k);
iterator it(myNode,this);
return it;
}
BinaryTreeMap::iterator BinaryTreeMap::put(const MapKey& k, const MapElem& e)
{
Node* nodes = binarySearchTreeFind(k)->parent;
if(nodes->entry.key() == k)
nodes->entry.data = e;
else if(nodes->isSentinel == true)
{
if(nodes->parent->leftChild->isSentinel == true && nodes->parent->rightChild->isSentinel == true)
versionNumber++;
nodes->isSentinel = false;
nodes->entry = (MapEntry(k, e));
Node* lChild = new Node(nodes);
Node* rChild = new Node(nodes);
nodes->leftChild = lChild;
nodes->rightChild = rChild;
n++;
}
iterator itr(nodes,this);
return itr;
}

void BinaryTreeMap::erase(const MapKey& k) throw(KeyNotFound)
{
iterator itr = find(k);
if(itr == end())
throw KeyNotFound("Bad Key Index");
else
if(itr != end())
erase(itr);
}

void BinaryTreeMap::erase(iterator& p) throw(PositionOutOfBounds)
{
iterator itr = p;
if(itr.theNode->leftChild->isSentinel == true && itr.theNode->rightChild->isSentinel == true)
{
Node *n = p.theNode->parent;
if(n->leftChild == p.theNode)
{
n->leftChild = p.theNode->rightChild;
}
else
{
n->rightChild = p.theNode->rightChild;
}
delete n;
versionNumber--;
}
else if(itr.theNode->leftChild->isSentinel == true && itr.theNode->rightChild->isSentinel == false)
{
delete p.theNode->leftChild;
p.theNode->parent->leftChild = p.theNode->rightChild;
delete p.theNode;
}
else if(itr.theNode->leftChild->isSentinel == false && itr.theNode->rightChild->isSentinel == true)
{
delete p.theNode->rightChild;
p.theNode->parent->rightChild = p.theNode->rightChild;
delete p.theNode;
}
else if(itr.theNode->leftChild->isSentinel == false && itr.theNode->rightChild->isSentinel == false)
{
p.theNode->parent->rightChild = p.theNode->rightChild;
delete p.theNode;
}
else if(p.theNode == root)
{
root = root->rightChild;
}

}


BinaryTreeMap::Node *BinaryTreeMap::binarySearchTreeFind(const MapKey& key)
{
Node *find = root;
while(find->isSentinel == false || find->entry.key() != key)
{
if(find->entry.key() > key)
find = find->leftChild;
else if(find->entry.key() < key)
find = find->rightChild;
}
return find;
}
BinaryTreeMap::Node *BinaryTreeMap::inOrderSuccessor(BinaryTreeMap::Node *start)
{
Node* hold = start;
if(hold->rightChild->isSentinel == false)
{
hold = start->rightChild;
while(hold->leftChild->isSentinel == false)
hold = hold->leftChild;
}
return hold;
}

BinaryTreeMap::Node *BinaryTreeMap::inOrderPredecessor(BinaryTreeMap::Node *start)
{
Node* hold = root;
if(start->leftChild->isSentinel == false)
{
hold = start->leftChild;
while(hold->rightChild->isSentinel != true)
hold = hold->leftChild;
}
return hold;
}

void BinaryTreeMap::deleteSubtree(BinaryTreeMap::Node *start)
{
iterator itr = begin();
itr.theNode = start;
if(itr.theNode->isSentinel != false)
{
deleteSubtree(itr.theNode->leftChild);
deleteSubtree(itr.theNode->rightChild);
delete itr.theNode;
}
if(itr.theNode->isSentinel == true)
{
delete itr.theNode->leftChild;
delete itr.theNode->rightChild;
}
}

BinaryTreeMap::iterator BinaryTreeMap::begin()
{
static int lastVersionNumber = -1;
static iterator beginning = end();

if(this->version() == lastVersionNumber)
{
return beginning;
}

if(n==0)
{
beginning = end();
} else {
Node *start = root;
while(start->leftChild->isSentinel==false)
{
start=start->leftChild;
}
beginning = iterator(start,this);
}
lastVersionNumber = version();
return beginning;
}

BinaryTreeMap::iterator BinaryTreeMap::end()
{
return iterator(NULL,this);
}

SequenceElem& BinaryTreeMap::iterator::operator*() throw(PositionOutOfBounds)
{
if(this->theBinaryTreeMap->version() != versionNumber)
throw PositionOutOfBounds("Structure has changed since iterator was created");

return theNode->entry;
}

BinaryTreeMap::iterator& BinaryTreeMap::iterator::operator++() throw(PositionOutOfBounds)
{
if(this->theBinaryTreeMap->version() != versionNumber)
throw PositionOutOfBounds("Structure has changed since iterator was created");

if(*this==theBinaryTreeMap->end())
throw PositionOutOfBounds("Can't Advance");

if(theNode->rightChild->isSentinel!=true)
{
theNode = theBinaryTreeMap->inOrderSuccessor(theNode);
} else if(theNode->parent!=NULL && theNode->parent->leftChild == theNode)
{
theNode = theNode->parent;
} else
{
while(theNode->parent!=NULL && theNode->parent->rightChild == theNode)
{
theNode = theNode->parent;
}
theNode = theNode->parent;
}
return *this;
}

BinaryTreeMap::iterator& BinaryTreeMap::iterator::operator--() throw(PositionOutOfBounds)
{
if(this->theBinaryTreeMap->version() != versionNumber)
throw PositionOutOfBounds("Structure has changed since iterator was created");

if(*this==theBinaryTreeMap->begin())
throw PositionOutOfBounds("Can't Retreat");

if(*this==theBinaryTreeMap->end())
{
theNode = theBinaryTreeMap->root;
while(theNode->rightChild->isSentinel != true)
{
theNode = theNode->rightChild;
}
return *this;
}

if(theNode->leftChild->isSentinel!=true)
{
theNode = theBinaryTreeMap->inOrderPredecessor(theNode);
} else if(theNode->parent!=NULL && theNode->parent->rightChild == theNode)
{
theNode = theNode->parent;
} else {
while(theNode->parent!=NULL && theNode->parent->leftChild == theNode)
{
theNode = theNode->parent;
}
theNode = theNode->parent;
}
return *this;
}



#pragma warning( disable : 4290 ) // C++ Doesn't support the specification of Exceptions and issues warnings that they aren't properly enforced. Disable the warnings

#include<string>

class RunTimeException {
public:
RunTimeException(std::string msg) : message(msg) {}
RunTimeException(char *msg) : message(msg) {}
std::string message;
};

class IndexOutOfBounds : public RunTimeException {
public:
IndexOutOfBounds(std::string msg) : RunTimeException(msg) {}
IndexOutOfBounds(char *msg) : RunTimeException(msg) {}
};

class PositionOutOfBounds : public RunTimeException {
public:
PositionOutOfBounds(std::string msg) : RunTimeException(msg) {}
PositionOutOfBounds(char *msg) : RunTimeException(msg) {}
};



class KeyNotFound : public RunTimeException {
public:
KeyNotFound(std::string msg) : RunTimeException(msg) {}
KeyNotFound(char *msg) : RunTimeException(msg) {}
};

~DSTypes.h~

#ifndef MAPTYPES
#define MAPTYPES
typedef std::string MapElem;
typedef std::string MapKey;
#endif

class MapEntry {
public:
MapEntry() { data = MapElem(); m_key = MapKey(); }
MapEntry(const MapKey& k, const MapElem& e) { data = e; m_key = k; }
const MapKey& key() { return m_key; }
MapElem data;

private:
MapKey m_key;
};

// This class will be used to create an object that will act as a "hash functio
class StringHash {
public:
int operator()( const std::string& x ) const
{
// Based on the formula for Java's String.hashCode()
// s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
int power=1;
size_t total =1;
for(int i=x.length()-1; i>=0; i--) {
total+=power*x[i];
power *= 31;
}
return total;
}
};

// Define the hash function object
typedef StringHash HashFunction;


typedef MapEntry SequenceElem;

[Drrockso]

You should use code blocks code and indentation.