//*******************************
//
//  bst.h 
//
//  header file for Binary_Search_Tree
// template class
//
// stolen from Mark Weiss text, then modified
// D. L. Frey  10/21/98
//
//*******************************
#ifndef BST_H
#define BST_H

#include <stdlib.h>	// for NULL
#include "bstnode.h"

const int FALSE = 0;
const int TRUE = 1;

template <class Etype>
class Binary_Search_Tree
{
  protected:
    // delete the nodes bottom-up (leafs first)
    void Make_Empty( Tree_Node<Etype> * & T );

    // Insert a new node into the tree
    // does nothing if Element already in the tree
    void Insert( const Etype & X, Tree_Node<Etype> * & T );

    // Inorder Traversal and print entire tree
    void Print_Tree( Tree_Node<Etype> * T ) const;

    // Find node that matched T->Element
    // returns node pointer if found; NULL if not
    Tree_Node<Etype> *
        Find( const Etype & X, Tree_Node<Etype> * T ) const;

    // count nodes in the tree
    int Count_Nodes (Tree_Node<Etype> *T);

    // private data
    Tree_Node<Etype> *Root;
    Tree_Node<Etype> *CurrentNode;  // last touched by Find, Insert

  public:
    // Default Constructor
    Binary_Search_Tree( ) : Root( NULL ), CurrentNode( NULL ) { }

    // Destructor.
    virtual ~Binary_Search_Tree( )
        { Make_Empty( Root ); Root = CurrentNode = NULL; }

    // Operators -- returns int to user
    virtual int Find( const Etype & X )
        { return int( CurrentNode = Find( X, Root ) ); }

    // insert element into tree -- use protected Insert
    // side-effect: CurrentNode is set
    virtual void Insert( const Etype & X )
        { Insert( X, Root ); }

    // print entire tree in-order traversal
    virtual void Print_Tree ()
	{ Print_Tree (Root); }

    // count and return number of nodes
    int Count_Nodes ()
	{ return Count_Nodes (Root); }

};

#endif