Syntax Issue with templated member class functions

[mjolnir91]

I'm working on a project for one of my classes and am running into a problem I've faced before but can no longer solve due to the use of templates.

The issue is with writing headers for functions that are being implemented outside of the class definition and have a return data type of a pointer to a private data member belonging to the class. Perhaps code will be the best explination:

#ifndef BINARYSEARCHTREE_H
#define BINARYSEARCHTREE_H
#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>
#include <sstream>
using namespace std;



template <class ItemType>
class BinarySearchTree
{
private:
struct BinaryNode
{
ItemType element;
BinaryNode *left;
BinaryNode *right;
BinaryNode(const ItemType &theElement, BinaryNode *lt, BinaryNode *rt): element(theElement), left(lt), right(rt) { }
};

BinaryNode *root;

// clone
BinaryNode* clone(const BinaryNode *rhsRoot)
{
if(rhsRoot == NULL)
return NULL;
else
return new BinaryNode(rhsRoot->element, clone(rhsRoot->left), clone(rhsRoot->right));
}// end clone

// privMakeEmpty
void privMakeEmpty(BinaryNode *&) const;
// privFindMax
BinaryNode * privFindMax(BinaryNode *) const;
// privFindMin
BinaryNode * privFindMin(BinaryNode *) const;
// privIsEmpty
bool privIsEmpty() const;
// privPrintTree
void privPrintTree(BinaryNode *) const;


public:
//-------------------Book Functions--------------------------
// Constructor
BinarySearchTree();
// Intializing Constructor
BinarySearchTree( const BinarySearchTree &rhs );
//Destructor
~BinarySearchTree();
// findMin
BinaryNode * findMin(BinaryNode*) const;
// findMax
BinaryNode * findMax(BinaryNode*) const;
//bool contains( const ItemType & x ) const;
// isEmpty
bool isEmpty() const;
//PrintTree
void printTreeIn() const;
//makeEmpty
void makeEmpty();
//insert
void insert(const ItemType & x);
//remove
void remove(const ItemType & x);
// operator= overload
const BinarySearchTree & operator=(const BinarySearchTree &rhs);

//--------------------Additional Funcitons------------------

// Print the contents to open stream out via a level order tranversal
void printTreeLevel(ostream &out) const;

// Returs the width, i.e, number of nodes in the largest level, of the tree
int width () const;

// Perform an LL rotation at the node containing x, if x is present and the
// rotation is possible.
// Return true on success, and false otherwise.
bool LLat (const ItemType &x);

// Perform a RR rotation at the node
// containing x, if x is present and the rotation is possible.
// Return true on success, and false otherwise.
bool RRat (const ItemType &x);

// Look up x in the Bst. If x is found, then anappropriate rotation (either LL or RR)
// is done at each node, starting from the parent px of x, along the path from px to
// root of the tree so that the result is a BST in which x is the root. Returns
// true if x is found, and false otherwise.

bool lookup (const ItemType& x);

};



Now directly below this code in the same Header file if I try to write this:
template <class ItemType>
BinarySearchTree<ItemType>::BinaryNode* BinarySearchTree<ItemType>::findMin() const
{
return privFindMin(root);

}// end findMind


The compiler throws and error saying "error C2143: syntax error: missing ';' before '*'.

Now I've had this error before in a simlar program where I wasn't using a templated class. To solve the error I did something like this....BinarySearchTree::BinaryNode * BinarySearchTree::privFindMin()

I did this because for some reason the compiler didn't seem to recognize the BinaryNode data type. However, with the addition of the extra BinarySearchTree:: it worked. But this fix is failing now because I have the <ItemType> and I guess its causing some other problems I don't know about. Anyone have any suggestions or insights into why this problem occurs. I know I could simply declare everything inside the class but I hate doing that and want to know the root of the problem.

[firedraco]

Use [code][/code] tags next time.

Anyway, try:
typename BinarySearchTree<ItemType>::BinaryNode* BinarySearchTree<ItemType>::findMin() const
and see if that works...

[mjolnir91]

Sorry this is my first forum post... Anyhow I tried what you said and it didn't work just said something about BinaryNode not being a type or something.

[jsmith]

The reason is because BinaryNode is declared private in the BinarySearchTree class.

[mjolnir91]

Well that being said is there anyway to write the functions outside of the class?

[jsmith]

Nope, not without making it public, which isn't a good idea.

[b2ee]

Did you try the following?

"
typename BinarySearchTree<ItemType>::BinaryNode* BinarySearchTree<ItemType>::findMin(BinaryNode*) const

"

It should work. "typename" should be used to tell the compiler the dependency and refer to a type.


B2ee