Getting this BST template to work.

Question

hI, I'm trying to get this code from Larry Nyhoff's book to compile in Bloodshed. It's actually been taken word for word from the author's website, though I declared it on .cpp instead of .h (the .h file ain't working with the tester application).

http://cs.calvin.edu/activities/books/c++/ds/2e/SourcePrograms/Chap12/

The search(const DataType & item) function is what's giving me grief. The compiler error says:

In member function `bool BST<DataType>::search(const DataType&) const': 
expected `;' before "locptr" 
`locptr' undeclared (first use this function)

What I'm I missing here?

 #include <iostream>

#ifndef BINARY_SEARCH_TREE
#define BINARY_SEARCH_TREE


template <typename DataType>
class BST
{
 public:
  /***** Function Members *****/
  BST();

  bool empty() const;

  bool search(const DataType & item) const;

  void insert(const DataType & item);

  void remove(const DataType & item);

  void inorder(std::ostream & out) const;

  void graph(std::ostream & out) const;

  private:
  /***** Node class *****/
  class BinNode 
  {
   public:
    DataType data;
    BinNode * left;
    BinNode * right;

    // BinNode constructors
    // Default -- data part is default DataType value; both links are null.
    BinNode()
    : left(0), right(0)
    {}

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


}; //end inner class

typedef BinNode * BinNodePointer; 

  /***** Private Function Members *****/
  void search2(const DataType & item, bool & found,
               BinNodePointer & locptr, BinNodePointer & parent) const;
 /*------------------------------------------------------------------------
   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.#include <iostream>
 ------------------------------------------------------------------------*/

  void inorderAux(std::ostream & out, 
                  BST<DataType>::BinNodePointer subtreePtr) const;
  /*------------------------------------------------------------------------
    Inorder traversal auxiliary function.

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

  void graphAux(std::ostream & out, int indent,
                      BST<DataType>::BinNodePointer subtreeRoot) const;
  /*------------------------------------------------------------------------
    Graph auxiliary function.

    Precondition:  ostream out is open; subtreePtr points to a subtree 
        of this BST.
    Postcondition: Graphical representation of subtree with root pointed 
        to by subtreePtr 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; //**THIS FAILS, WHY?**//
   bool found = false;
   while (!found && locptr != 0)
   {
      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;
}




#endif

Answer 1

Put a typename before the declaration:

typename BST<DataType>::BinNodePointer locptr = myRoot;

The point is that due to potential template specialization, the compiler cannot know that the dependent identifier BinNodePointer identifies a type.