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 directions\n";
            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

This code is an implementation and test driver of a doubly linked list. This list is pointer based and uses dynamic memory.

Sorted Doubly Linked List with Insertion and Deletion

#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;

class Dllist
{
 private:
 typedef struct Node
 {
 string name;
 Node* next;
 Node* prev;
 };
 Node* head;
 Node* last;
 public:
 Dllist()
 {
 head = NULL;
 last = NULL;
 }
 bool empty() const { return head==NULL; }
 friend ostream& operator<<(ostream& ,const Dllist& );
 void Insert(const string& );
 void Remove(const string& );
};

void Dllist::Insert(const string& s)
{
 // Insertion into an Empty List.
 if(empty())
 {
 Node* temp = new Node;
 head = temp;
 last = temp;
 temp->prev = NULL;
 temp->next = NULL;
 temp->name = s;
 }
 else
 {
 Node* curr;
 curr = head;
 while( s>curr->name && curr->next != last->next) curr = curr->next;

 if(curr == head)
 {
 Node* temp = new Node;
 temp->name = s;
 temp->prev = curr;
 temp->next = NULL;
 head->next = temp;
 last = temp;
 //  cout<<" Inserted "<<s<<" After "<<curr->name<<endl;
 }
 else
 {
 if(curr == last && s>last->name)
 {
 last->next = new Node;
 (last->next)->prev = last;
 last = last->next;
 last->next = NULL;
 last->name = s;
 //  cout<<" Added "<<s<<" at the end "<<endl;
 }
 else
 {
 Node* temp = new Node;
 temp->name = s;
 temp->next = curr;
 (curr->prev)->next = temp;
 temp->prev = curr->prev;
 curr->prev = temp;
 //  cout<<" Inserted "<<s<<" Before "<<curr->name<<endl;
 }
 }
 }
}

ostream& operator<<(ostream& ostr, const Dllist& dl )
{
 if(dl.empty()) ostr<<" The list is empty. "<<endl;
 else
 {
 Dllist::Node* curr;
 for(curr = dl.head; curr != dl.last->next; curr=curr->next)
 ostr<<curr->name<<" ";
 ostr<<endl;
 ostr<<endl;
 return ostr;
 }
}

void Dllist::Remove(const string& s)
{
 bool found = false;
 if(empty())
 {
 cout<<" This is an empty list! "<<endl;
 return;
 }
 else
 {
 Node* curr;
 for(curr = head; curr != last->next; curr = curr->next)
 {
 if(curr->name == s)
 {
 found = true;
 break;
 }
 }
 if(found == false)
 {
 cout<<" The list does not contain specified Node"<<endl;
 return;
 }
 else
 {
 // Curr points to the node to be removed.
 if (curr == head && found)
 {
 if(curr->next != NULL)
 {
 head = curr->next;
 delete curr;
 return;
 }
 else
 {
 delete curr;
 head = NULL;
 last = NULL;
 return;
 }
 }
 if (curr == last && found)
 {
 last = curr->prev;
 delete curr;
 return;
 }
 (curr->prev)->next = curr->next;
 (curr->next)->prev = curr->prev;
 delete curr;
 }
 }
}

int main()
{
 Dllist d1;
 int ch;
 string temp;
 while(1)
 {
 cout<<endl;
 cout<<" Doubly Linked List Operations "<<endl;
 cout<<" ------------------------------"<<endl;
 cout<<" 1. Insertion "<<endl;
 cout<<" 2. Deletion "<<endl;
 cout<<" 3. Display "<<endl;
 cout<<" 4. Exit "<<endl;
 cout<<" Enter your choice : ";
 cin>>ch;
 switch(ch)
 {
 case 1: cout<<" Enter Name to be inserted : ";
 cin>>temp;
 d1.Insert(temp);
 break;
 case 2: cout<<" Enter Name to be deleted : ";
 cin>>temp;
 d1.Remove(temp);
 break;
 case 3: cout<<" The List contains : ";
 cout<<d1;
 break;
 case 4: system("pause");
 return 0;
 break;
 }
 }

This code is a simple example of how to safely open a text file in C++. Notice the very important check that the file was opened correctly. This covers a range of errors,  most commonly file not found.

// Read integers from file and print sum.

#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>

using namespace std;

int main() {
 int sum = 0;
 string word;
 ifstream inFile;

 inFile.open("test.txt");
 if (!inFile) {
 cout << "Unable to open file";
 exit(1); // terminate with error
 }

 while (inFile >> word) {
 cout << word << " ";
 }

 inFile.close();

 return 0;
}

this snippet of code is an alternative to system(“pause”) in MS Visual Studio.

/*
* File:   SystemPause.cpp
* Author: B Turley
*
* This function can be used as a substitute for 'system("pause")'
* in Microsoft Visual Studio
*
* Created on November 10, 2009, 1:17 AM
*/

#include <iostream>
#include <limits>
using namespace std;

void pause()
{
cout<<"Press any key to Continue...";
cin.sync();
cin.ignore(numeric_limits<streamsize> ::max(), '\n');
}

int main(int argc, char** argv) {

pause();

return (0);
}

This little piece of code can convert a string of decimal characters into an integer value.  If you seek to convert a string into a double, see this post.

/*
 * A function to convert a string into an integer
 */

#include <string>

int StringToInt (std::string str)
{
    int total = 0;
    int length = str.length(); // the length of the string
    int x = 1; // this is our multiplier, used to convert each digit into tens, units, etc
    for (int i = 1; i < str.length(); i++)
        x *= 10; // initialise x correctly

    for (int i = 0; i < length; i++)
    { // loop through the string
        // 48 is the base value (ASCII)
        // multiply it by x to get it into tens, units, etc
        total += (static_cast <int> (str[i]) - 48) * x;
        x /= 10; // divide x by 10, to reduce the units by one
    }

    return total; // return the value as an integer
}

/** EXAMPLE USAGE **/
#include <iostream>
int main ()
{
    int t = StringToInt("1234") + 300;
    std::cout < < t; // should be 1534 (1234 + 300 = 1534)

    std::cin.get ();
    return EXIT_SUCCESS;
}

This C++ class is a good demonstration of Object Orientation in code.

Download the  entire code: RadioClass.zip

// definition file for class Radio
#ifndef RADIO_H
#define RADIO_H
#include <iostream>
using namespace std;

const bool FM = true;
const bool AM = false;
const bool ON = true;
const bool OFF = false;
const int MIN_VOLUME = 0;
const int MAX_VOLUME = 11; // it goes to eleven!

class Radio
{
public:
	// constructors:
	Radio();
	Radio(bool b,bool p,double fm,double am,int v);

	// accessors:
	bool getBand();
	bool getPower();
	double getFMStation();
	double getAMStation();
	int getVolume();

	// mutators:
	bool setBand(bool b);
	bool setPower(bool p);
	bool setFMStation(double s);
	bool setAMStation(double s);
	bool setVolume(int v);

	// utility functions:
	void displayRadio();

private:
	bool band; // FM = true, AM = false
	bool power; // on = true, off = false
	double FMstation , AMstation ; // as per norms
	int volume; // 0..11 is the valid range
};
#endif

// Implementation file for class Radio
#include <iostream>
#include "Radio.h"
using namespace std;

// constructors:
Radio::Radio()
{
	band = FM;
	volume = 4;
	power = OFF;
	FMstation = 88.1;
	AMstation = 530;
}

bool Radio::setFMStation(double s)
{
	if((s < 88.1) || (s > 107.9))  // Station's input out of range
		return false;
	if((int(s * 10) % 2) == 0)     // station's .x is even and therefore invalid
		return false;
	FMstation = s;
	return true;
}
bool Radio::setAMStation(double s)
{
	if((s &lt; 530) || (s &gt; 1600))
		return false;
	if((int(s) % 10) != 0) // AMstation not divisible by 10 and therefore invalid
		return false;
	AMstation = s;
	return true;
}

// utility functions:
void Radio::displayRadio()
{
	cout << "Band = " <<; ((band == FM) ? "FM":"AM") << endl;
	cout &lt;&lt; "Power = " &lt;&lt; ((power == ON) ? "ON":"OFF") &lt;&lt; endl;
	cout &lt;&lt; "FM Station = " &lt;&lt; FMstation &lt;&lt; endl;
	cout &lt;&lt; "AM Station = " &lt;&lt; AMstation &lt;&lt; endl;
	cout &lt;&lt; "Volume = " &lt;&lt; volume &lt;&lt; endl &lt;&lt; endl;
}

// mutators:
bool Radio::setBand(bool b)
{
	band = b;
	return true;
}
bool Radio::setPower(bool p)
{
	power = p;
	return true;
}
bool Radio::setVolume(int v)
{
	if((v < MIN_VOLUME) || (v > MAX_VOLUME))
		return false;
	volume = v;
	return true;
}
//custom constructor , placed later on purpose.
Radio::Radio(bool b,bool p,double fm,double am,int v) // build a radio with custom defaults
{
	band = FM;
	setBand(b);
	power = OFF;
	setPower(p);
	FMstation = 88.1;
	setFMStation(fm);
	AMstation = 530;
	setAMStation(am);
	volume = 4;
	setVolume(v);
}
// accessors:
bool Radio::getBand()
{
	return band;
}
bool Radio::getPower()
{
	return power;
}
double Radio::getFMStation()
{
	return FMstation;
}
double Radio::getAMStation()
{
	return AMstation;
}
int Radio::getVolume()
{
	return volume;
}

// Driver file for class Radio
#include <iostream>
#include "Radio.h"
using namespace std;

//Radio object driver, this file sends the commands that "push the radio buttons" via function calls.

void main()
{
	Radio myJamBox;              // Build a radio to be referred to as 'myJamBox'.

	myJamBox.displayRadio();     // display myJamBox's current attributes.
	myJamBox.setAMStation(550);  // adjust's myJamBox's AM station to 530
	myJamBox.setPower(ON);       // flips myJamBox's power swith ON
	myJamBox.displayRadio();     // display myJamBox's current attributes.

	system("pause");

}