binary search tree w/ iterators and parent-aware children

bst.hpp

#ifndef BST_H
#define BST_H

#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <queue>
using namespace std;

template <class TKey>
class bst {
	private:
		struct node {
			node() { key=TKey(); link[0]=link[1]=NULL; parent=NULL; }
			operator TKey () { return key; }
			void print();

			TKey key;
			node *link[2];
			node *parent;
		};

	public:
		class iterator : public bst {
			public:
				iterator() : p(NULL) {}
				node * operator*() { return p; }
				iterator & operator++();
				bool operator!=(const iterator & rhs) const
						{ return p != rhs.p; }

			private:
				friend class bst<TKey>;
				iterator(node *p) : p(p) {}
				node *p;
		};

		iterator begin() { return minmax_key(Troot,0); }
		iterator end() { return (minmax_key(Troot,1))->link[1]; }

		bst() { Troot=NULL; }
		~bst() { clear(Troot); }

		bool empty() { return Troot==NULL; }
		void clear() { clear(Troot); Troot=NULL; }

		void erase(TKey &key);
		void insert(TKey &key);

		void print_inorder() { print_inorder(Troot); }
		void print_bylevel();
//		void print_iterator();

	private:
		void clear(node *);

		node *minmax_key(node *, int);
		node *erase(node *, TKey &);
		node *insert(node *, TKey &);

		void print_inorder(node *);

		node *Troot;
};

template<class TKey>
class bst<TKey>::iterator & bst<TKey>::iterator::operator++()
{
	bst<TKey>::node * tmpnode;

	if (p == NULL) {
//		cout << "\n\ngoing to set to minkey\n\n";
		p = minmax_key(p,0);					// set to min key

	} else if (p->link[1] != NULL) {				// check if there's a right child

		p = p->link[1];						// move to right child
		while (p->link[0] != NULL)				// check if theres a left child (possibly multiple)
			p = p->link[0];					// move to the farthest left

	} else {

		tmpnode = p->parent;					// assign tmpnode to p-> parent to move back up tree
		while (tmpnode != NULL && p == tmpnode->link[1]) {	// if tmpnode==null, were at Troot
			p = tmpnode;
			tmpnode = tmpnode->parent;			// keep going up
		}
		p = tmpnode;
	}
	return *this;
}

template <class TKey>
void bst<TKey>::node::print()
{
#ifdef PRINTDETAILS
    cout << setw(3) << key << " :";

    if (parent == NULL) cout << " P=" << setw(3) << "NA";
    else		 cout << " P=" << setw(3) << parent->key;
    if (link[0]) cout << " L=" << setw(3) << link[0]->key;
	else         cout << "      ";
    if (link[1]) cout << " R=" << setw(3) << link[1]->key;
	else         cout << "      ";

    cout << endl;
#else
	cout << key << endl;
#endif
}

template <class TKey>
void bst<TKey>::clear(node *T)
{
	if (T) {
		clear(T->link[0]);
		clear(T->link[1]);
		delete T;
		T = NULL;
	}
}

template <class TKey>
class bst<TKey>::node *bst<TKey>::minmax_key(node *T, int dir)
{
	if (T) {
		while (T->link[dir])
			T = T->link[dir];
	}

	return T;
}

template <class TKey>
void bst<TKey>::erase(TKey &key)
{ 
	Troot = erase(Troot, key);
}

template <class TKey>
class bst<TKey>::node *bst<TKey>::erase(node *T, TKey &key)
{
	node *Tm;

	if (T == NULL) {
		cerr << "key " << key << " not found" << endl;
	} else if (T->key != key) {
		int dir = T->key < key;
		T->link[dir] = erase(T->link[dir], key);
		if (T->link[dir])					// T has a child still
			T->link[dir]->parent = T;			// (re)make links between children and parent

	} else {
		if (T->link[0] && T->link[1]) {
			Tm = minmax_key(T->link[0], 1);
			T->key = Tm->key;

/******************************************************************************/
			if (Tm->link[0])				// if maxkey has a child, it'd be a left one
				Tm->link[0]->parent = Tm->parent;	// must update it since its parent got moved
//			cout << "T->key now = " << T->key << endl;
/******************************************************************************/

			T->link[0] = erase(T->link[0], T->key);

/******************************************************************************/
			if (T->link[0]) {				// T has a LC still
				T->link[0]->parent = T;
			}
			if (T->link[1]) {				// T has a RC still
				T->link[1]->parent = T;
			}
/******************************************************************************/

		} else {
			Tm = T;
			if (T->link[0]) {				// T only has a LC
				T=T->link[0];
				T->parent = Tm;
			} else if (T->link[1]) {			// T only has a RC
				T=T->link[1];
				T->parent = Tm;
			} else {
				T=NULL;					// T is a leaf node
			}
			delete Tm;
		}
	}
	return T;
}

template <class TKey>
void bst<TKey>::insert(TKey &key)
{
	Troot = insert(Troot, key); 
}

template <class TKey>
class bst<TKey>::node *bst<TKey>::insert(node *T, TKey &key)
{
	if (T == NULL) {
		T = new node;
		T->key = key;
	} else if (T->key == key) {
		cerr << "key " << key << " already in tree" << endl;
	} else {
		int dir = T->key < key;
		T->link[dir] = insert(T->link[dir], key);
		T->link[dir]->parent = T;					// set parent info of node
	}

	return T;
}

template <class TKey>
void bst<TKey>::print_inorder(node *T)
{
	if (T) {
		print_inorder(T->link[0]);
		T->print();
		print_inorder(T->link[1]);
	}
}

template <class TKey>
void bst<TKey>::print_bylevel()
{
	if (Troot == NULL)
		return;

	queue<node *> Q;
	node *T;

	Q.push(Troot);
	while (!Q.empty()) {
		T = Q.front();
		Q.pop();

		T->print();
		if (T->link[0]) Q.push(T->link[0]);
		if (T->link[1]) Q.push(T->link[1]);
	}
}

//template <class TKey>
//void bst<TKey>::print_iterator()
//{
//	iterator iter;
//	iter = begin();
//	while (iter != end()) {
//		cout << (*iter)->key << endl;
//		++iter;
//	}
//}

#endif