Threaded Binary Search Tree in C++

/*********************************************************************************************************
* Threaded Binary Search Tree Implementation *
* Programmer: Graham Nedelka *
* Created in April, 2013 *
* Computer Science 116: Data Structures *
*********************************************************************************************************/
#include <iostream>
#include <iomanip>

using namespace std;

struct bstNode{
// This constructs a ‘node’ container to serve as reference points for a threaded binary search
// tree. Theoretically, each node will point to another container known as a ‘child.’ In this case
// the children are located to the left and to the right of the current node. The nodes to the left
// of the current node contain integers smaller than itself, and larger to the right. What differentiates
// this implementation from binary search tree is the ‘threaded’ aspect, where the nodes within the
// in-order binary tree point to their predecessors, instead of pointing to NULL by default. This allows
// for a shorter processing time in retrieval of data. If a child to the right of the current node has
// no left children, it will point to the current node via a left thread because data to be traversed or
// accessed in that direction is unavailable. The opposite is true for the children to the left of the
// current node.
//
// Left: accepts a node that has been determined to contain a smaller integer than the current
// node and assigns the ‘left’ pointer to its location. GetLeft returns this node when called.
//
// Right: ccepts a node that has been determined to contain a larger integer than the current
// node and assigns the ‘right’ pointer to its location. GetRight returns this node when called.
//
// LeftThread: accepts a boolean value, denoting that the current node is infact a left thread.
//
// ReturnLeftThread: returns the boolean value passed into LeftThread.
//
// RightThread: accepts a boolean value, denoting that the current node is infact a right thread.
//
// ReturnRightThread: returns the boolean value passed into RightThread.

int data;
bool lthread;
bool rthread;
bstNode *left;
bstNode *right;
bstNode(int value){
lthread = false;
rthread = false;
data = value;
left = NULL;
right = NULL;
};
int GetData() {return data;}
void SetLeft(bstNode *l){left = l;}
void SetRight(bstNode *r){right = r;}
bstNode *GetLeft() {return left;}
bstNode *GetRight() {return right;}
void LeftThread(bool value){lthread = value;}
void RightThread(bool value){rthread = value;}
bool ReturnLeftThread() {return lthread;}
bool ReturnRightThread() {return rthread;}
bool IsLeft(){
if(left == NULL)
return false;
else
return true;
}
bool IsRight(){
if(right == NULL)
return false;

return true;
}
};

class BinarySearchTree{
// This represents the threaded binary search tree ADT (Abstract Data Type), which can be thought
// of as an actual tree of information. In this case, the nodes and the edges between them are
// branches where each bend in the branch contains a node with an integer value within it. After
// each number has been dealt with and sorted according to value, the nodes furthest from the pivot
// point at the top of the tree (ironically called the ‘root’), are called leaves. The root is set
// to NULL by default, but with every integer that is passed in, the binary search tree sets the
// root to the current value, thereby creating a ‘sub-tree’ of the ADT in it’s entirety.
//
// Insert: accepts an integer value to be inserted into the tree by creating a new bstNode, which is
// compared to the contents of the most recently created (active) node and placed either to the left
// or to the right within the tree.
//
// Display: displays the contents of the nodes within the binary search tree by traversing through it.
//
// Search: accepts an integer value, which is searched for within the binary search tree.

public:
BinarySearchTree(){root = NULL;};
void Insert(int);
void Display();
bstNode* Search(int key);
bstNode* root;
bstNode* current;
};

void BinarySearchTree::Insert(int value){
bstNode *node = new bstNode(value);
// If the root does not exist, it is an empty tree — create a new node.
if (root == NULL){
root = node;
return;
}
bstNode *pointer = root, *parent = NULL;
// Begin while loop.
// Compares current value to root, which can be the root of a sub-tree.
while (pointer != NULL){
if(value == pointer->GetData()){
cout << “—————————————————————-” << endl;
cout << “Error: attempted to insert duplicate value: ” << value <<” — Ignored.” << endl;
cout << “—————————————————————-” << endl;
delete node;
return;
}
parent = pointer;
if(value < pointer->GetData()){
if(pointer->ReturnLeftThread())
break;
else
pointer = pointer->GetLeft();}
else{
if(pointer->ReturnRightThread())
break;
else{
pointer = pointer->GetRight();}
}
}
// End while loop.
// Determine the location of the current node compared to that of it’s parent, thereby
// making a thread between them if applicable.
if (pointer == NULL){
if (value < parent->GetData()){
parent->SetLeft(node);
node->SetRight(parent);
node->RightThread(true);
}
else{
parent->SetRight(node);
node->SetLeft(parent);
node->LeftThread(true);
}
}
else{
if (value < pointer->GetData()){
node->SetLeft(pointer->GetLeft());
node->LeftThread(true);
node->SetRight(pointer);
node->RightThread(true);
pointer->SetLeft(node);
pointer->LeftThread(false);
}
else{
node->SetRight(pointer->GetRight());
node->RightThread(true);
node->SetLeft(pointer);
node->LeftThread(true);
pointer->SetRight(node);
pointer->RightThread(false);
}
}
return;
}

void BinarySearchTree::Display(){
cout << “\nNodes In Order: ” << setw(19) << “Threads:” << endl;
if(root == NULL){
cout << “Empty” << endl;
return;
}
bstNode *currentRoot, *currentParent;
currentRoot = root;
do{
while(currentRoot != NULL){
currentParent = currentRoot;
if(currentRoot->ReturnLeftThread())
break;
else
currentRoot = currentRoot->GetLeft();
}
// Print threads associated with the ordered data.
cout << setw(8) << currentParent->data << setw(30) << “Right thread of “<< currentParent->right->data << “\n”;
currentRoot = currentParent->GetRight();
while(currentParent->ReturnRightThread()){
cout << setw(8) << currentRoot->data << setw(29) << “Points left to ” << currentRoot->left->data << “\n”;
currentParent = currentRoot;
currentRoot = currentParent->GetRight();
}
}
while(currentRoot != NULL);
}

bstNode* BinarySearchTree::Search(int value){
bstNode* current = root;
while (current) {
if(current->data == value){
cout << current->data << ” does exist!” << endl;
return current;
}
else if (value < current->data){
current = current->left;
}
else current = current->right;
}
cout << “\n” << setw(5) << “(” << value << “) was not found.” << endl;
cout << “—————————————————————-” << endl;
return NULL;
}

main(){
BinarySearchTree a;

cout << “\nThreaded Binary Tree Implementation \n” << endl;
int c;
int b[] = {90, 12, 42, 98, 45, 32, 131, 131, 101, 59, 74, 10, 8, 1, 22, 100};
for (int c = 0; c < (sizeof(b)/sizeof(*b)); ++c){
a.Insert(b[c]);
}
a.Display();
cout << “\nThreaded Binary Tree Implementation \n” << endl;

for (int i = 0; i < (sizeof(b)/sizeof(*b)); i++) {
a.Search(b[i]);
}
return 0;
}

Advertisements

Tags: , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: