\special{landscape}
\documentclass[landscape,letterpaper]{article}
\pagestyle{empty}
\topmargin  -0.75in
\evensidemargin -0.75in
\oddsidemargin -0.75in
\textheight 8in
\textwidth  10.5in
\headheight 0in
\headsep    0in
\begin{document}
\begin{Large}
%%\end{verbatim}\newpage\begin{verbatim}
\begin{verbatim}
// -----------------------------------------------------------------------
//
// Binary search tree template classes
// File: BinSearchTree/bstree.h
//
// -----------------------------------------------------------------------

#ifndef _BSTREE_H
#define _BSTREE_H

#include <assert.h>
#include "queStack.h"
typedef unsigned int UINT;

// -----------------------------------------------------------------------

// forward declarations

template <class T> class BTree;
template <class T> class BTreeIterator;
template <class T> class PreorderIterator;
template <class T> class InorderIterator;
template <class T> class PostorderIterator;
template <class T> class LevelIterator;

\end{verbatim}\newpage\begin{verbatim}
template <class T>
class BTnode
{
  friend class BTree<T>;
  friend class BTreeIterator<T>;
  friend class PreorderIterator<T>;
  friend class InorderIterator<T>;
  friend class PostorderIterator<T>;
  friend class LevelIterator<T>;

  friend ostream& operator<< (ostream&, const BTree<T>&);

  T		data;		// all members
  BTnode<T>	*le;		// are private
  BTnode<T>	*ri;

  // constructors

  BTnode () {}
  BTnode (const T& t, BTnode<T> *l, BTnode<T> *r) : data(t) { le=l; ri=r; }
};

\end{verbatim}\newpage\begin{verbatim}
template <class T>
class BTree
{
    friend class BTreeIterator<T>;
    friend class PreorderIterator<T>;
    friend class InorderIterator<T>;
    friend class PostorderIterator<T>;
    friend class LevelIterator<T>;
 
    BTnode<T>   *LEAF;  // sentinel, LEAF->ri is also the root pointer
 
    UINT         size;  // number of nodes
    UINT         ht;    // height of tree
 
    // ------------------------------------------------------------------
 
    typedef BTreeIterator<T> *iterptr;
    list< iterptr > iterlist;
 
    // ------------------------------------------------------------------
 
    int          depth;
 
    void doEmpty    (BTnode<T>*);       // recursive aux. functions
    void redoHeight (BTnode<T>*, UINT);
    void prePrint   (BTnode<T>*);
\end{verbatim}\newpage\begin{verbatim}
// class BTree continued ...
  public:

    BTree ();			// constructor
   ~BTree ();			// destructor

    T& operator[] (const BTreeIterator<T>& it)	// return "curr" element
      { return it.curr->data; }			// pointed to by iterator

    void    insert  (const T&);		// insert in sorted tree
    bool remove  (const T&);		// remove first instance

    bool search  (const T&);
    bool isEmpty () { return bool(LEAF->ri==LEAF); }

    UINT    nNodes  () { return size; }
    UINT    height  () { return ht; }

    void makeEmpty ();
    void print     () { prePrint(LEAF->ri); }
};

\end{verbatim}\newpage\begin{verbatim}
template <class T>		// Base class for all iterator classes
class BTreeIterator
{
    friend class BTree<T>;

  protected:

    stack_queue<list<BTnode<T>*> > stque;
    BTree<T>		*tree;
    BTnode<T>		*curr;

  public:

    BTreeIterator (BTree<T>&);
    virtual ~BTreeIterator ();

    void reset ();

    bool atEnd () { return bool (curr==tree->LEAF); }

    virtual BTreeIterator<T>& operator++ () = 0;

    operator== (const BTreeIterator<T>& it) { return (curr==it.curr); }
};

\end{verbatim}\newpage\begin{verbatim}
template <class T>
class PreorderIterator : public BTreeIterator<T>
{
  public:

    PreorderIterator (BTree<T>& bt) : BTreeIterator<T>(bt) { reset(); }

    BTreeIterator<T>& operator++ ();
};

// -----------------------------------------------------------------------

template <class T>
class InorderIterator : public BTreeIterator<T>
{
  public:

    InorderIterator (BTree<T>& bt) : BTreeIterator<T>(bt) { reset(); }

    BTreeIterator<T>& operator++ ();
};

// -----------------------------------------------------------------------

template <class T>
class PostorderIterator : public BTreeIterator<T>
{ public:

    PostorderIterator (BTree<T>& bt) : BTreeIterator<T>(bt) { reset(); }

    BTreeIterator<T>& operator++ ();
};
\end{verbatim}\newpage\begin{verbatim}
template <class T>
class LevelIterator : public BTreeIterator<T>
{
  public:

    LevelIterator (BTree<T>& bt) : BTreeIterator<T>(bt) { reset(); }

    BTreeIterator<T>& operator++ ();
};

\end{verbatim}\newpage\begin{verbatim}
// BTree<T> member functions: doEmpty, redoHeight


template <class T>
void BTree<T>::doEmpty (BTnode<T> *s)
{
  if (s == LEAF) return;

  doEmpty (s->le);	// recursively deletes each node
  doEmpty (s->ri);	// in a POSTORDER traversal

  delete s;
}

// ----------------------------------------------------------------------

template <class T>
void BTree<T>::redoHeight (BTnode<T> *s, UINT d)
{
  if (s == LEAF) return;

  redoHeight (s->le, d+1);	// recursively re-computes
  redoHeight (s->ri, d+1);	// the height of the tree

  if (d > ht) ht = d;
}
\end{verbatim}\newpage\begin{verbatim}
// BTree<T> member functions: prePrint


template <class T>			// prints the tree in
void BTree<T>::prePrint (BTnode<T> *s)	// PREORDER
{
  if (s == LEAF) return;

  ++depth;

  cout << depth << "\t" << s->data << "\t--->\t";

  if (s->le == LEAF)
    cout << "<LEAF>" << "\t";
  else
    cout << s->le->data << "\t";

  if (s->ri == LEAF)
    cout << "<LEAF>" << endl;
  else
    cout << s->ri->data << endl;

  prePrint (s->le);
  prePrint (s->ri);

  --depth;
}
\end{verbatim}\newpage\begin{verbatim}
// BTree<T> member functions: constructor, destructor


template <class T>              // constructor
BTree<T>::BTree ()
{
  LEAF = new BTnode<T>;
  LEAF->le = LEAF;
  LEAF->ri = LEAF;      // "root" pointer
  size = ht = 0;
  depth = -1;
}
 
// ----------------------------------------------------------------------
 
template <class T>              // destructor
BTree<T>::~BTree ()
{
  doEmpty (LEAF->ri);
 
  delete LEAF;
 
  // reset iterators referring to this tree
  list<iterptr>::iterator p;
  for(p = iterlist.begin(); p != iterlist.end(); p++)
  {
    (*p)->curr = NULL;
    (*p)->tree = NULL;
  }
}
\end{verbatim}\newpage\begin{verbatim}
template <class T>			// inserts "tval" into the
void BTree<T>::insert (const T& tval)	// sorted binary tree
{					// LEAF is used as sentinel
  BTnode<T> *p = LEAF;
  BTnode<T> *c = LEAF->ri;
  LEAF->data = tval;
  UINT h = 0;

  while (c != LEAF)
  {
    p = c;
    c = (tval < c->data) ? c->le : c->ri;
    ++h;
  }

  c = new BTnode<T>(tval, LEAF, LEAF);
  assert (c);

  if (tval < p->data)
    p->le = c;
  else
    p->ri = c;

  // reset all iterators

  list<iterptr>::iterator it;
  for (it=iterlist.begin(); it!=iterlist.end(); it++)
    (*it)->reset ();

  ++size;
  if (h > ht) ht = h;	// adjust height
}
\end{verbatim}\newpage\begin{verbatim}
// BTree<T> member functions: remove


template <class T>			  // removes the first instance
bool BTree<T>::remove (const T& tval)  // of "tval"
{
  BTnode<T> *p = LEAF;
  BTnode<T> *c = LEAF->ri;
  LEAF->data = tval;

  while (tval != c->data)
  {
    p = c;
    c = (tval < c->data) ? c->le : c->ri;
  }

  if (c == LEAF) return false;		// not found

  BTnode<T> *t = c;

  if (t->ri == LEAF)			// case #1
  {
    c = c->le;
  }
  else if (t->ri->le == LEAF)		// case #2
  {
    c = c->ri;
    c->le = t->le;
  }
\end{verbatim}\newpage\begin{verbatim}
// BTree<T>::remove continued...
  else					// case #3
  {
    BTnode<T> *q = c->ri;

    while (q->le->le != LEAF)
      q = q->le;

    c = q->le;
    q->le = c->ri;
    c->le = t->le;
    c->ri = t->ri;
  }

  if (tval < p->data)
    p->le = c;
  else
    p->ri = c;

  delete t;

  // reset all iterators
  list<iterptr>::iterator it;
  for (it=iterlist.begin(); it!=iterlist.end(); it++)
    (*it)->reset ();

  ht = 0;
  redoHeight (LEAF->ri, 0);
  --size;

  return true;
}
\end{verbatim}\newpage\begin{verbatim}
// BTree<T> member functions: search, makeEmpty


template <class T>
bool BTree<T>::search (const T& tval)
{
  BTnode<T> *p = LEAF->ri;
  LEAF->data = tval;

  while (tval != p->data)
    p = (tval < p->data) ? p->le : p->ri;

  if (p == LEAF) return false;
  return true;
}
// ----------------------------------------------------------------------

template <class T>
void BTree<T>::makeEmpty ()
{
  doEmpty (LEAF->ri);

  // reset all iterators
  list<iterptr>::iterator p;
  for (p=iterlist.begin(); p!=iterlist.end(); p++)
  {
    (*p)->stque.makeEmpty();
    (*p)->curr = LEAF;
  }
  size = 0;
  ht = 0;
}
\end{verbatim}\newpage\begin{verbatim}
// BTreeIterator functions: constructor, destructor


template <class T>
BTreeIterator<T>::BTreeIterator (BTree<T>& t) : tree(&t)
{
  (t.iterlist).push_front(this);
}
 
// ----------------------------------------------------------------------
 
template <class T>
BTreeIterator<T>::~BTreeIterator ()
{
  stque.makeEmpty ();
 
  // find iterator record
 
  list< BTree<T>::iterptr >::iterator p = find(tree->iterlist.begin(),
                                               tree->iterlist.end(),
                                               this);
  tree->iterlist.erase(p);
 
}
\end{verbatim}\newpage\begin{verbatim}
// Iterator functions: reset, ++ (preorder)


template <class T>
void BTreeIterator<T>::reset ()
{
  curr = tree->LEAF;
  stque.makeEmpty ();
  ++(*this); // operator++ ();
}

// ----------------------------------------------------------------------

template <class T>
BTreeIterator<T>& PreorderIterator<T>::operator++ ()
{
  if (curr->ri != tree->LEAF) stque.push (curr->ri);
  if (curr->le != tree->LEAF) stque.push (curr->le);

  if (stque.isEmpty ())
    curr = tree->LEAF;
  else
    curr = stque.pop ();

  return *this;
}
\end{verbatim}\newpage\begin{verbatim}
// Iterator functions ++ (inorder)


template <class T>
BTreeIterator<T>& InorderIterator<T>::operator++ ()
{
  BTnode<T> *p = curr->ri;
  while (p != tree->LEAF)
  {
    stque.push (p);
    p=p->le;
  }

  if (stque.isEmpty ())
    curr = tree->LEAF;
  else
    curr = stque.pop ();

  return *this;
}
\end{verbatim}\newpage\begin{verbatim}
// Iterator functions ++ (postorder)


template <class T>
BTreeIterator<T>& PostorderIterator<T>::operator++ ()
{
  BTnode<T> *p = tree->LEAF;

  if (!stque.isEmpty ())
    p = stque.pop ();

  if (p->ri!=tree->LEAF && curr!=p->ri)
  {
    stque.push (p);
    p = p->ri;

    while (p!=tree->LEAF)
    {
      stque.push (p);

      if (p->le!=tree->LEAF)
        p = p->le;
      else
        p = p->ri;
    }
    p = stque.pop ();
  }

  curr = p;

  return *this;
}
\end{verbatim}\newpage\begin{verbatim}
// Iterator functions ++ (levelorder)

template <class T>
BTreeIterator<T>& LevelIterator<T>::operator++ ()
{
  if (curr->le != tree->LEAF) stque.append (curr->le);
  if (curr->ri != tree->LEAF) stque.append (curr->ri);

  if (stque.isEmpty ())
    curr = tree->LEAF;
  else
    curr = stque.pop ();

  return *this;
}


#endif
\end{verbatim}
%%\end{verbatim}\newpage\begin{verbatim}
\end{Large}
\end{document}
