template <class T> class BinarySearchNode
{
public:
T* theNode;
BinarySearchNode* theLesserNodePointer;
BinarySearchNode* theGreaterNodePointer;
BinarySearchNode(T* theContents)
{
if(theContents==NULL)
{
return;
}
theNode= new T();
*theNode=theContents;
//theLesserNodePointer= new BinarySearchNode();
theLesserNodePointer->theNode=NULL;
//theGreaterNodePointer= new BinarySearchNode();
theGreaterNodePointer->theNode=NULL;
}
};
template <class T> class BinarySearchTree
{
public:
BinarySearchNode<T>* theRootNode;
BinarySearchTree(T* theRootNodeContents)
{
if(theRootNodeContents!=NULL)
theRootNode= new BinarySearchNode<T>(theRootNodeContents);
}
BinarySearchNode<T>* findNode(T* theContents)
{
// gc is for sissies who are too scared to handle memory related stuff and all...
//pointers rule...!!!!!!!
// going the recursive way will give us
//all stack related headaches and what not...blah blah blah
//the logic is the same though...phoooey
if(theContents==NULL || theRootNode==NULL)
{
return NULL; //:|
}
BinarySearchNode<T>* temp=theRootNode;
T value=*theContents;
if(*(temp->theNode)==theContents)
{
return temp; //we have a match sergeant
}
else if(*(temp->theNode)>value)
{
//to the left keep goin
temp=temp->theLesserNodePointer;
while(temp!=NULL && *(temp->theNode)>value)
{
temp=temp->theLesserNodePointer==NULL?NULL:temp->theLesserNodePointer;
}
//u reach the node where eventually temp shud be null
//or temp shud be the answer since it shud equal it right...
///mmmmmmmmmmmmm now u get it
return temp;
}
else if(*(temp->theNode)<value)
{
//to the left keep goin
temp=temp->theGreaterNodePointer;
while(temp!=NULL && *(temp->theNode)<value)
{
temp=temp->theGreaterNodePointer==NULL?NULL:temp->theGreaterNodePointer;
}
// what are u looking at....theres an explanation somewhere above
return temp;
}
}
void insertNode(T* theContents)
{
//T shud implement comparison operators :|
if(theContents==NULL)
{
return;
}
BinarySearchNode<T>* temp=theRootNode;
if(temp==NULL)
{
//create a new root done
this=BinarySearchTree(theContents);
}
BinarySearchNode<T>* previous=theRootNode;
T value=*theContents;
if(*(temp->theNode)>value)
{
//to the left keep goin
previous=temp;
temp=temp->theLesserNodePointer;
while(temp!=NULL && *(temp->theNode)>=value)
{
previous=temp;
temp=temp->theLesserNodePointer==NULL?NULL:temp->theLesserNodePointer;
}
//u reach the node where eventually temp shud be null
//and since the same is done for every node prior to this
//this shud be the only approachable case neglecting
//murky stuff which can happen unknown to u and me
temp= new BinarySearchNode<T>(theContents);
temp->theGreaterNodePointer= new BinarySearchNode<T>(previous->theNode);
temp->theGreaterNodePointer->theLesserNodePointer=temp; //obs duhhhhhh
}
else if(*(temp->theNode)<value)
{
//to the left keep goin
previous=temp;
temp=temp->theGreaterNodePointer;
while(temp!=NULL && *(temp->theNode)<value)
{
previous=temp;
temp=temp->theGreaterNodePointer==NULL?NULL:temp->theGreaterNodePointer;
}
//u reach the node where eventually temp shud be null
//and since the same is done for every node prior to this
//this shud be the only approachable case neglecting
//murky stuff which can happen unknown to u and me
temp= new BinarySearchNode<T>(theContents);
temp->theLesserNodePointer= new BinarySearchNode<T>(previous->theNode);
temp->theLesserNodePointer->theGreaterNodePointer=temp; //obs duhhhhhh
}
}
};