This is my personal implementation of a binary search tree. My tree uses iteration instead of recursion for its insertion, deletion and searches for faster execution because function stack overhead is avoided. Recursion is still used for tree deletion because I didn’t want to implement a stack for the traversal of the tree which is required for deletion.
// SearchableADT test driver
// Copyright (C) 2011 Kyle Turley
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program. If not, see <http://www.gnu.org/licenses/>.
// Purpose:
// this test driver is used to emperically test the performance of various
// searchable abstract data structures that adhere to the SearchableADT
// interface.
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include "BST.h"
using namespace std;
void menu_Loop(), menu_Choices(char ans);
void load_dict(), clr_dict(), find_a_word(), find_from_file(), tree_stats(), end_program();
bool isfound(string findme);
//declare a new SearchableADT to test
SearchableADT<string> *dictionary = new BST<string>;
int main() {
menu_Loop();
return 0;
}//end main
void menu_Loop() {
char ans; //declare ans variable, this will be used OVER AND OVER
do {
cout << "--- ADT Tinkering Menu ---" << endl;
cout << "1: Load a Dictionary File" << endl;
cout << "2: Clear Dictionary" << endl;
cout << "3: Check for an Entry" << endl;
cout << "4: Check for Entries from File" << endl;
cout << "5: Report Tree Statistics" << endl;
cout << "6: Option 6 - Exit" << endl; //print us some options
cin >> ans; //take in an answer
cin.ignore(80, 'n');
menu_Choices(ans);
} while (ans != '6'); //keep on running on till they pick exit!
}// end menu_Loop()
void menu_Choices(char ans) {
switch (ans)//roll thru options
{
case '1':
load_dict();
break;
case '2':
clr_dict();
break;
case '3':
find_a_word();
break;
case '4':
find_from_file();
break;
case '5':
tree_stats();
break;
case '6':
end_program();
break;
default://THEY DIDNT READ THE MENU, WHO WOULD HAVE THOUGHT?!?!
cout << "Please read and follow all directionsn";
break;
}
}// end menu_Choices(char ans)
//functions, FILL WITH VALUABLE PROGRAMMING SKILLS
// Asks the user for a filename, then loads each whitespace delineated string into the SearchableADT
void load_dict() {
string filename = "";
fstream in;
clock_t start, finish;
while (!in.is_open()) {
cout << "Enter a valid C++ file to Load" << endl;
cin >> filename;
in.open(filename.c_str());
}
start = clock();
dictionary->loadFromFile(filename);
finish = clock();
in.close();
cout << "## file added to ADT ##" << endl;
cout << "Load time: " << ((double) (finish - start) / CLOCKS_PER_SEC) << "sec" << endl;
}
// releases all memory occupied by the SearchableADT
void clr_dict() {
clock_t start, finish;
start = clock();
dictionary->clear();
finish = clock();
cout << "## ADT CLEARED ##" << endl;
cout << "time: " << ((double) (finish - start) / CLOCKS_PER_SEC) << "sec" << endl;
}
// Asks the user for a word
void find_a_word() {
string findme;
cout << "Enter a string to search for" << endl;
cin >> findme;
clock_t start, finish;
start = clock();
// insert timing code here
if(isfound(findme)){
cout << "found it" << endl;
}else
cout << "not found" << endl;
finish = clock();
cout << "time: " << ((double) (finish - start) / CLOCKS_PER_SEC) << "sec" << endl;
}
void find_from_file() {
string filename = "";
fstream in;
clock_t start, finish;
stringstream buffer;
string temp;
int misspelled_count = 0;
while (!in.is_open()) {
cout << "Enter a valid Text file to Read" << endl;
cin >> filename;
in.open(filename.c_str());
}
buffer << in.rdbuf();
in.close();
start = clock();
// attempt to find each word
while (buffer.good()) {
buffer >> temp;
if(!isfound(temp)){
cout << temp << " isn't in the dictionary" << endl;
misspelled_count++;
}
}
finish = clock();
cout << misspelled_count << " misspelled words were found" << endl;
cout << "Search time: " << ((double) (finish - start) / CLOCKS_PER_SEC) << "sec" << endl;
}
void tree_stats() {
clock_t start, finish;
start = clock();
cout << "Number of Entries: " << dictionary->numEntries() << endl;
finish = clock();
cout << "Report time: " << ((double) (finish - start) / CLOCKS_PER_SEC) << "sec" << endl;
}
bool isfound(string findme){
bool isfound = false;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
// make findme lowercase
for (int i = 0; i < strlen(findme.c_str()); i++) {
if (findme[i] >= 0x41 && findme[i] <= 0x5A)
findme[i] = findme[i] + 0x20;
}
//if findme contains a ? character, generate a list of 26 possibilities to search for
if (findme.find_first_of('?') != string::npos) {
string possibilities[25];
int qmarkindex = findme.find_first_of('?');
for (int i = 0; i < 25; i++) {
possibilities[i] = findme.replace(qmarkindex, 1, 1, alphabet[i]);
if (dictionary->isThere(possibilities[i])){
cout << possibilities[i] << endl;
isfound = true;
}
}
} else // no '?' character was found,
isfound = dictionary->isThere(findme);
return isfound;
}
void end_program(){
dictionary->clear(); // release memory stored by the dictionary
exit(0);
}
// Abstract Searchable ADT interface
// Copyright (C) 2011 Kyle Turley
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program. If not, see <http://www.gnu.org/licenses/>.
#ifndef SEARCHABLEADT_H
#define SEARCHABLEADT_H
#include <string>
using namespace std;
template <typename T>
class SearchableADT{
public:
// these are all purely virtual functions that must be implemented by all classes that inherit from SearchableADT().
virtual int loadFromFile(string filename) = 0;
virtual void clear(void) = 0;
virtual void insertEntry(T value) = 0;
virtual void deleteEntry(T value) = 0;
virtual bool isThere(T value) = 0 ;
virtual int numEntries(void) = 0;
private :
//no private methods or data members.
};
#endif
// BST class
// Copyright (C) 2011 Kyle Turley
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program. If not, see <http://www.gnu.org/licenses/>.
#ifndef BST_H
#define BST_H
#pragma once
#include "SearchableADT.h"
#include <cstring>
using namespace std;
template <typename T>
class binarynode {
public:
T data;
binarynode<T> *left;
binarynode<T> *right;
};
template <typename T>
class BST : public SearchableADT<T> {
public:
BST(void);
~BST(void);
int loadFromFile(string filename);
void clear(void);
void insertEntry(T value);
void deleteEntry(T value);
bool isThere(T value);
int numEntries(void);
// additional methods, not part of abstract interface
void postorder_delete(binarynode<T>* itr);
int BST<T>::height(binarynode<T>* itr);
private:
binarynode<T> * root_ptr;
double numnodes;
};
template <typename T>
BST<T>::BST(void) {
root_ptr = NULL;
numnodes = 0;
}
template <typename T>
BST<T>::~BST(void) {
this->clear();
}
template <typename T>
int BST<T>::loadFromFile(string filename) {
fstream in;
vector<T> vect;
vector<T>::const_iterator iter;
std::stringstream buffer;
string temp;
in.open(filename.c_str());
buffer << in.rdbuf();
// read each word into a vector
while (buffer.good()) {
buffer >> temp;
vect.push_back(temp);
}
// randomize the vector for more efficient inserts
// just in case the user tries to input a sorted file.
// "A good programmer looks both ways before crossing a one way street"
srand(time(0));
random_shuffle(vect.begin(), vect.end());
//now insert each randomized entry into the BST
for (iter = vect.begin(); iter != vect.end(); ++iter) {
//cout << *iter << endl;
this->insertEntry(*iter);
}
return 0;
}
template <typename T>
void BST<T>::clear(void) {
this->postorder_delete(root_ptr);
root_ptr = NULL;
//numnodes = 0;
return;
}
template <typename T>
void BST<T>::insertEntry(T value) {
// create the new node to be inserted and populate it with data
binarynode<T> *temp, *prev, *curr;
temp = new binarynode<T>;
temp->data = value;
temp->left = NULL;
temp->right = NULL;
// insert the node into its proper place in the tree
if (root_ptr == NULL) {
// the tree is empty so make the new node the root
root_ptr = temp;
} else {
// discover the new nodes proper place in a binary search fashion
curr = root_ptr;
while (curr != NULL) {
prev = curr;
if (temp->data < curr->data)
curr = curr->left;
else
curr = curr->right;
}
// the proper place has been found at this point. insert the new node
if (temp->data < prev->data)
prev->left = temp;
else
prev->right = temp;
}
numnodes++;
return;
}
template <typename T>
void BST<T>::deleteEntry(T value) {
binarynode<T> *prev, *curr, *grandparent;
prev = curr = grandparent = NULL;
binarynode<T> *deleteme = new binarynode<T>;
deleteme->data = value;
// discover where the node should be in a binary search fashion
curr = root_ptr;
while (curr != NULL) {
grandparent = prev;
prev = curr;
if (deleteme->data < curr->data)
curr = curr->left;
else if (deleteme->data > curr->data)
curr = curr->right;
else
break;
}
if (deleteme->data == prev->data) {// found it, now delete it. There are special cases for different children
if (prev->left == NULL && prev->right == NULL) { //no children
if (grandparent->left->data == prev->data)
grandparent->left = NULL;
else
grandparent->right = NULL;
delete prev;
} else if (prev->left == NULL && prev->right != NULL) { //right child exists
if (grandparent->left->data == prev->data)
grandparent->left = prev->right;
else
grandparent->right = prev->right;
delete prev;
} else if (prev->left != NULL && prev->right == NULL) { //left child exists
if (grandparent->right->data == prev->data)
grandparent->right = prev->left;
else
grandparent->left = prev->left;
delete prev;
}
}
numnodes--;
}
template <typename T>
bool BST<T>::isThere(T value) {
binarynode<T> *prev, *curr;
curr = root_ptr;
// find the right spot in an iterative fashion
// recursion should be avoided whenever possible for safety and performance
while (curr != NULL) {
prev = curr;
if (value < curr->data)
curr = curr->left;
else if (value > curr->data)
curr = curr->right;
else if (prev->data == value)
return true; // value was found
}
return false; //value wasn't found
}
template <typename T>
int BST<T>::numEntries(void) {
// do a post-order traversal counting along the way
// this is kinda hacked, but I want to preserve the given SearchableADT interface
cout << "Tree Height: " << height(root_ptr) << endl;
return numnodes;
}
template <typename T>
void BST<T>::postorder_delete(binarynode<T>* itr) {
if (itr != NULL) {
postorder_delete(itr->left);
postorder_delete(itr->right);
delete itr;
numnodes--;
}
return;
}
template <typename T>
int BST<T>::height(binarynode<T>* itr) {
if (itr == NULL)
return -1;
else
return 1 + max(height(itr->left), height(itr->right));
}
#endif