BinarySearchTree.cpp

#include <iostream>
using namespace std;

#define T Tree<Key, Value>
#define KEY_VALUE template <class Key, class Value>

KEY_VALUE
class Tree {
  public:
    Tree *parent;
    Tree *left;
    Tree *right;

    Key key;
    Value value;

    Tree(Key k, Value v) {
      parent = NULL; left = NULL; right = NULL;
      key = k;
      value = v;
    }

    T * Retrieve(const Key k) {
      if (k < key)
        return (left == NULL) ? NULL : left->Retrieve(k);
      if (k > key)
        return (right == NULL) ? NULL : right->Retrieve(k);

      return this;
    }

    void Insert(Tree **tree, Tree *parent, const Key k, const Value v) {
      if (*tree == NULL) {
        T *tmp = new T(k, v);
        tmp->parent = parent;
        *tree = tmp;
      } else {
        (*tree)->Insert(k, v);
      }
    }

    void Insert(Key k, Value v) {
      if (k < key) Insert(&left, this, k, v);
      else Insert(&right, this, k, v);
    }

    void Print(Key k) {
      T *tmp = Retrieve(k);
      if (tmp == NULL)
        cout << "Not found." << endl;
      else
        cout << tmp->value << endl;
    }
};

int main(int argc, char **argv) {
  Tree<string, int> root("H", 8);

  root.Insert("C", 3);
  root.Insert("A", 1);
  root.Insert("F", 6);
  root.Insert("D", 4);
  root.Insert("G", 7);
  root.Insert("J", 10);
  root.Insert("O", 14);
  root.Insert("N", 13);

  root.Print("A");
  root.Print("N");
  root.Print("H");
  root.Print("F");

  cout << "Root:  " << &root << endl;
  cout << "Match: " << root.left->parent << endl;

  return 0;
}