Figure 12.1& 7 Binary Search Tree Class Template

/* BST.h contains the declaration of class template BST.
   Basic operations:
     Constructor: Constructs an empty BST
     empty:       Checks if a BST is empty
     search:      Search a BST for an item
     insert:      Inserts a value into a BST
     remove:      Removes a value from a BST
     inorder:     Inorder traversal of a BST -- output the data values
     graph:       Output a grapical representation of a BST
   Private utility helper operations:
     search2:     Used by delete
     inorderAux:  Used by inorder
     graphAux:    Used by graph
  Other operations described in the exercises:
     destructor
     copy constructor
     assignment operator
     preorder, postorder, and level-by-level traversals
     level finder
---------------------------------------------------------------------------*/

#include <iostream>

#ifndef BINARY_SEARCH_TREE
#define BINARY_SEARCH_TREE

template <typename DataType>
class BST
{
 private:
  /***** Node structure *****/
  class BinNode 
  {
   public:
    DataType data;
    BinNode * left;
    BinNode *  right;

    // BinNode constructors
    // Default -- data part undefined; both links null
    BinNode()
    : left(0), right(0)
    {}

    // Explicit Value -- data part contains item; both links null
    BinNode(DataType item)
    : data(item), left(0), right(0)
    {}
  };

  typedef BinNode * BinNodePointer; 

 public:
  /***** Function Members *****/
  BST();
  /*------------------------------------------------------------------------
    Construct a BST object.

    Precondition:  None.
    Postcondition: An empty BST has been constructed.
   -----------------------------------------------------------------------*/

  bool empty() const;
  /*------------------------------------------------------------------------
    Check if BST is empty.

    Precondition: None.
    Postcondition: Returns true if BST is empty and false otherwise.
   -----------------------------------------------------------------------*/

  bool search(const DataType & item) const; 
  /*------------------------------------------------------------------------
    Search the BST for item.

    Precondition:  None.
    Postcondition: Returns true if item found, and false otherwise.
   -----------------------------------------------------------------------*/

   void insert(const DataType & item);
  /*------------------------------------------------------------------------
    Insert item into BST.

    Precondition:  None.
    Postcondition: BST has been modified with item inserted at proper 
        position to maintain BST property. 
  ------------------------------------------------------------------------*/

  void remove(const DataType & item);
  /*------------------------------------------------------------------------
    Remove item from BST.

    Precondition:  None.
    Postcondition: BST has been modified with item removed (if present);
        BST property is maintained.
    Note: remove uses auxiliary function search2() to locate the node
          containing item and its parent.
 ------------------------------------------------------------------------*/

  void inorder(ostream & out);
  /*------------------------------------------------------------------------
    Inorder traversal of BST.

    Precondition:  ostream out is open.
    Postcondition: BST has been inorder traversed and values in nodes 
        have been output to out.
    Note: inorder uses private auxiliary function inorderAux().
 ------------------------------------------------------------------------*/

  void graph(ostream & out);
  /*------------------------------------------------------------------------
    Graphic output of BST.

    Precondition:  ostream out is open.
    Postcondition: Graphical representation of BST has been output to out.
    Note: inorder uses private auxiliary function graphAux().
 ------------------------------------------------------------------------*/

 private:
  /***** Private Function Members *****/
  void search2(const DataType & item, bool & found,
               BinNodePointer & locptr, BinNodePointer & parent);
 /*------------------------------------------------------------------------
   Locate a node containing item and its parent.
 
   Precondition: None.
   Postcondition: locptr points to node containing item or is null if 
       not found, and parent points to its parent
 ------------------------------------------------------------------------*/

  void inorderAux(ostream & out, BinNodePointer subtreePtr);
  /*------------------------------------------------------------------------
    Inorder traversal auxiliary function.

    Precondition:  ostream out is open; subtreePtr points to a subtree 
        of this BST.
    Postcondition: Subtree of this BST with subtreePtr as root has been
        output to out.
 ------------------------------------------------------------------------*/

  void graphAux(ostream & out, int indent, BinNodePointer subtreeRoot);
  /*------------------------------------------------------------------------
    Graph auxiliary function.

    Precondition:  ostream out is open; subtreePtr points to a subtree 
        of this BST.
    Postcondition: Graphical representation of subtree of this BST with 
        subtreePtr as root has been output to out, indented indent spaces.
 ------------------------------------------------------------------------*/

 /***** Data Members *****/
  BinNodePointer myRoot; 

}; // end of class template declaration

//--- Definition of constructor
template <typename DataType>
inline BST<DataType>::BST()
: myRoot(0)
{}

//--- Definition of empty()
template <typename DataType>
inline bool BST<DataType>::empty() const
{ return myRoot == 0; }

//--- Definition of search()
template <typename DataType>
bool BST<DataType>::search(const DataType & item) const
{
  BST<DataType>::BinNodePointer locptr = myRoot;
  bool found = false;
  for (;;)
  {
    if (found || locptr == 0) break;
    if (item < locptr->data)       // descend left
      locptr = locptr->left;
    else if (locptr->data < item)  // descend right
      locptr = locptr->right;
    else                           // item found
      found = true;
  }
  return found;
}

//--- Definition of insert()
template <class DataType>
inline void BST<DataType>::insert(const DataType & item)
{
   BST<DataType>::BinNodePointer 
        locptr = myRoot,   // search pointer
        parent = 0;        // pointer to parent of current node
   bool found = false;     // indicates if item already in BST
   while (!found && locptr != 0)
   {
      parent = locptr;
      if (item < locptr->data)       // descend left
         locptr = locptr->left;
      else if (locptr->data < item)  // descend right
         locptr = locptr->right;
      else                           // item found
         found = true;
   }
   if (!found)
   {                                 // construct node containing item
      locptr = new BST<DataType>::BinNode(item);  
      if (parent == 0)               // empty tree
         myRoot = locptr;
      else if (item < parent->data )  // insert to left of parent
         parent->left = locptr;
      else                           // insert to right of parent
         parent->right = locptr;
   }
   else
      cout << "Item already in the tree\n";
}

//--- Definition of remove()
template <class DataType>
void BST<DataType>::remove(const DataType & item)
{
   bool found;                      // signals if item is found
   BST<DataType>::BinNodePointer 
      x,                            // points to node containing
      parent;                       //    "    " parent of x and xSucc
   search2(item, found, x, parent);

   if (!found)
   {
      cout << "Item not in the BST\n";
      return;
   }
   //else
   if (x->left != 0 && x->right != 0)
   {                                // node has 2 children
      // Find x's inorder successor and its parent
      BST<DataType>::BinNodePointer xSucc = x->right;
      parent = x;
      while (xSucc->left != 0)       // descend left
      {
         parent = xSucc;
         xSucc = xSucc->left;
      }

     // Move contents of xSucc to x and change x 
     // to point to successor, which will be removed.
     x->data = xSucc->data;
     x = xSucc;
   } // end if node has 2 children

   // Now proceed with case where node has 0 or 2 child
   BST<DataType>::BinNodePointer 
      subtree = x->left;             // pointer to a subtree of x
   if (subtree == 0)
      subtree = x->right;
   if (parent == 0)                  // root being removed
      myRoot = subtree;
   else if (parent->left == x)       // left child of parent
      parent->left = subtree; 
   else                              // right child of parent
      parent->right = subtree;
   delete x;
}

//--- Definition of inorder()
template <class DataType>
inline void BST<DataType>::inorder(ostream & out)
{ 
   inorderAux(out, myRoot); 
}

//--- Definition of graph()
template <class DataType>
inline void BST<DataType>::graph(ostream & out)
{ graphAux(out, 0, myRoot); }

//--- Definition of search2()
template <class DataType>
void BST<DataType>::search2(const DataType & item, bool & found,
                            BST<DataType>::BinNodePointer & locptr, 
			    BST<DataType>::BinNodePointer & parent)
{
   locptr = myRoot;
   parent = 0;
   found = false;
   while (!found && locptr != 0)
   {
      if (item < locptr->data)       // descend left
      {
         parent = locptr;
         locptr = locptr->left;
      }
      else if (locptr->data < item)  // descend right
      {
         parent = locptr;
         locptr = locptr->right;
      }
      else                           // item found
         found = true;
   }
}

//--- Definition of inorderAux()
template <class DataType>
void BST<DataType>::inorderAux(ostream & out, 
                               BST<DataType>::BinNodePointer subtreeRoot)
{
   if (subtreeRoot != 0)
   {
      inorderAux(out, subtreeRoot->left);    // L operation
      out << subtreeRoot->data << "  ";      // V operation
      inorderAux(out, subtreeRoot->right);   // R operation
   }
}

//--- Definition of graphAux()
#include <iomanip>

template <class DataType>
void BST<DataType>::graphAux(ostream & out, int indent, 
                             BST<DataType>::BinNodePointer subtreeRoot)
{
  if (subtreeRoot != 0)
    {
      graphAux(out, indent + 8, subtreeRoot->right);
      out << setw(indent) << " " << subtreeRoot->data << endl;
      graphAux(out, indent + 8, subtreeRoot->left);
    }
}

#endif 

Figure 12.8 Testing Binary Search Tree Class Template

/*----- treetester.cpp ----------------------------
  Program for testing class template BST.
  ------------------------------------------------*/
#include <iostream>
using namespace std;

#include "BST.h"

/*---- PART 3 ----
                                 // makeCopy() is a function with a
void makeCopy(BST<int> aBST)     // BST value parameter
{                                // to test the copy constructor
  cout << "\nNow copying the BST and adding 38999,"
          " -12312, and 55657 to the copy:\n";
  aBST.insert(38999);
  aBST.insert(-12312);
  aBST.insert(55657);
  cout << "--Inorder Traversal of the copy: \n";
  aBST.inorder(cout);
}
---- END PART 3 ----*/

int main()
{
  // Testing Constructor and empty()
  BST<int> intBST;            // test the class constructor
  cout << "Constructing empty BST\n";
  cout << "BST " << (intBST.empty() ? "is" : "is not") << " empty\n";

  // Testing inorder
  cout << "Inorder Traversal of BST: \n";
  intBST.inorder(cout);

  // Testing insert
  cout << "\nNow insert a bunch of integers into the BST."
          "\nTry items not in the BST and some that are in it:\n";
  int number;
  for (;;)
  {
    cout << "Item to insert (-999 to stop): ";
    cin >> number;
    if (number == -999) break;
    intBST.insert(number);
  }
  intBST.graph(cout);

  cout << "BST " << (intBST.empty() ? "is" : "is not") << " empty\n";
  cout << "Inorder Traversal of BST: \n";
  intBST.inorder(cout);

  cout << endl;

  // Testing search()
  cout << "\n\nNow testing the search() operation."
          "\nTry both items in the BST and some not in it:\n";
  for (;;)
  {
    cout << "Item to find (-999 to stop): ";
    cin >> number;
    if (number == -999) break;
    cout << (intBST.search(number) ? "Found" : "Not found") << endl;
  }

  // Testing remove()
  cout << "\nNow testing the remove() operation."
          "\nTry both items in the BST and some not in it:\n";
  for (;;)
  {
    cout << "Item to remove (-999 to stop): ";
    cin >> number;
    if (number == -999) break;
    intBST.remove(number);
    intBST.graph(cout);
  }
  cout << "\nInorder Traversal of BST: \n";
  intBST.inorder(cout);
  cout << endl;

/* ---- PART 1 ----
  // Testing Preorder and Postorder
  cout << "\nInorder Traversal of BST: \n";
  intBST.inorder(cout);
  cout << "\nPreorder Traversal of BST: \n";
  intBST.preorder(cout);
  cout << "\nPostorder Traversal of BST: \n";
  intBST.postorder(cout);
  cout << endl;
---- END PART 1 ----*/


/* ---- PART 2 ----
  // Testing the Destructor
  cout << "\nNow testing the destructor.  Remember to add an output\n"
          "statement to your destructor to indicate when it is called.\n";
  {
    BST<int> anotherBST;
    anotherBST.insert(6); anotherBST.insert(9); anotherBST.insert(5);
    anotherBST.insert(1); anotherBST.insert(3); anotherBST.insert(7);
    cout << "\nInorder Traversal of another BST: \n";
    anotherBST.inorder(cout);
    cout << "\n\nLifetime of this BST is over -- now destroy it.\n";
  }
---- END PART 2 ----*/


/* ---- PART 3 ----
  // Testing the Copy Constructor
  cout << "\nNow testing the copy constructor.\n";
  cout << "-- First with an initializing declaration: "
          "BST<int> copy = intBST;\n";
  BST<int> copy = intBST;
  cout << "-- Inorder traversal of copy:\n";
  copy.inorder(cout);
  cout << "\n\n-- Now by passing intBST to a value parameter:\n";
  makeCopy(intBST);
  cout << "\n--Check that original BST hasn't been changed.\n"
          "-- Inorder traversal of original:\n";
  intBST.inorder(cout);
  cout << endl;
---- END PART 3 ----*/


/* ---- PART 4 ----
  // Testing the Assignment Operator
  cout << "\nNow testing the assignment constructor with the statement:\n"
          "        copy = anotherBST = intBST;\n";
  BST<int> anotherBST;
  copy = anotherBST = intBST;
  cout << "\n-- Inorder traversal of intBST:\n";
  intBST.inorder(cout);
  cout << endl;
  cout << "\n-- Inorder traversal of anotherBST:\n";
  anotherBST.inorder(cout);
  cout << endl;
  cout << "\n-- Inorder traversal of copy:\n";
  copy.inorder(cout);
  cout << endl;
  cout << "\Now testing self-assignment with:  copy = copy;\n";
  copy = copy;
  cout << endl;
  cout << "\n-- Inorder traversal of copy:\n";
  copy.inorder(cout);
  cout << endl;  
---- END PART 4 ----*/

} 

Figure 12.9 Validating Computer Logins

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

/*---------------------------------------------------------------------
  Program to validate computer user-ids and passwords.  A list of
  valid ids and passwords is read from UsersFile and is stored in
  a BST.  When user-ids and passwords are entered during execution,
  this BST is searched to determine whether they are legal.
 
   Input (file):     UserInfo records for valid users
   Input (keyboard): Ids and passwords of users logging in
   Output (screen):  Messages indicating whether user-ids and
                       passwords are valid
 --------------------------------------------------------------------*/

//----- Class containing user information -----//
//      with >>, ==, and < operators
class UserInfo
{
 public: 
  // ***** Function Members and Friends ***** //
  //--- id accessor
  string id() const { return myId; }

  //--- input function
  void read(istream & in)
  {
    in >> myId >> myPassword;
  }

  //--- equals operator
  bool operator==(const UserInfo & user) const
  { return myId == user.myId &&
           myPassword == user.myPassword; }

  //--- less-than operator
  bool operator<(const UserInfo & user) const
  { return myId < user.myId ||
           myId == user.myId && myPassword < user.myPassword; }

  private: 
  // ***** Data Members ***** //
  string myId,
         myPassword;
};

//--- Definition of input operator
istream & operator>>(istream & in, UserInfo & user)
{
  user.read(in);
}


#include "BST.h"

int main()
{
  // Open stream to file of legal user-ids and password
  string userFile;
  cout << "Enter name of user-info file: ";
  getline(cin, userFile);
  ifstream inStream(userFile.data());
  if (!inStream.is_open())
  {
    cerr << "Cannot open " << userFile << "\n";
    exit(1);
  }

  // Build the BST of user records
  BST<UserInfo> userTree;   // BST of user records
  UserInfo user;            // a user record
  for(;;)
  {
    inStream >> user;
    if (inStream.eof()) break;

    userTree.insert(user);
  }

  // Validate logins
  cout << "Enter Q Q to stop processing.\n";
  for (;;)
  {
    cout << "\nUser id & password: ";
    cin >> user;
    if (user.id() == "Q") break;
    if (userTree.search(user))
      cout << "Valid user\n";
    else
      cout << "Not a valid user\n";
  }
}