Question about Binary Search Tree template

[ncwolfe]

I'm using Visual Studio 2005. I tried to adapt the existing class for the binary search tree (from my book) to a template and mostly it works, but I'm getting errors related to the insertNode and deleteSubTree functions when I try to build it.

The header file:

// Specification file for the IntBinaryTree class
#ifndef INTBINARYTREE_H
#define INTBINARYTREE_H
#include <stdlib.h>


template <class T>
class IntBinaryTree
{
private:
   struct TreeNode
   {
      T empOb;         // The value in the node
      TreeNode *left;    // Pointer to left child node
      TreeNode *right;   // Pointer to right child node
   };

   TreeNode *root;       // Pointer to the root node
   
   // Private member functions
   void insert(TreeNode *&, TreeNode *&);
   void destroySubTree(TreeNode *);
   void deleteNode(T, TreeNode *&);
   void makeDeletion(TreeNode *&);

   
public:
   // Constructor
   IntBinaryTree()
   {
	   root = NULL; 
   }
      
   // Destructor
   ~IntBinaryTree()
   {
	   destroySubTree(root); 
   }
	
      
   // Binary tree operations
   void insertNode(T);
   bool searchNode(T);
   void remove(T);
   
};
#endif

The relevant code from the .cpp:

template <class T>
void IntBinaryTree<T>::destroySubTree(TreeNode *nodePtr)
{
   if (nodePtr)
   {
      if (nodePtr->left)
         destroySubTree(nodePtr->left);
      if (nodePtr->right)
         destroySubTree(nodePtr->right);
      delete nodePtr;
   }
}

void IntBinaryTree<T>::remove(T emp)
{
   deleteNode(emp, root);
}

template <class T>
void IntBinaryTree<T>::deleteNode(T emp, TreeNode *&nodePtr)
{
   if (emp < nodePtr->value)
      deleteNode(emp, nodePtr->left);
   else if (emp > nodePtr->value)
      deleteNode(emp, nodePtr->right);
   else
      makeDeletion(nodePtr);
}

template <class T>
void IntBinaryTree<T>::insert(TreeNode *&nodePtr, TreeNode *&newNode)
{
   if (nodePtr == NULL)
      nodePtr = newNode;                  // Insert the node.
   else if (newNode->value < nodePtr->value)
      insert(nodePtr->left, newNode);     // Search the left branch
   else 
      insert(nodePtr->right, newNode);    // Search the right branch
}


template <class T>
void IntBinaryTree<T>::insertNode(T emp)
{
   TreeNode *newNode;      // Pointer to a new node.

   // Create a new node and store num in it.
   newNode = new TreeNode;
   newNode->value = emp;
   newNode->left = newNode->right = NULL;
   
   // Insert the node.
   insert(root, newNode);
}

And the errors:
1>EmployeeBinTree.obj : error LNK2019: unresolved external symbol "public: void __thiscall IntBinaryTree<class Employee>::insertNode(class Employee)" (?insertNode@?$IntBinaryTree@VEmployee@@@@QAEXVEmployee@@@Z) referenced in function _main
1>EmployeeBinTree.obj : error LNK2019: unresolved external symbol "private: void __thiscall IntBinaryTree<class Employee>::destroySubTree(struct IntBinaryTree<class Employee>::TreeNode *)" (?destroySubTree@?$IntBinaryTree@VEmployee@@@@AAEXPAUTreeNode@1@@Z) referenced in function "public: __thiscall IntBinaryTree<class Employee>::~IntBinaryTree<class Employee>(void)" (??1?$IntBinaryTree@VEmployee@@@@QAE@XZ)

Have I forgotten something? Is there a typo I'm not spotting, or did I do my template wrong? Any help is appreciated. Thanks.

[Murtan]

Templates require the users to see all of the member functions. You can't have the methods 'hidden' in a c++ file.

If the code creating the instance of the template doesn't "see" the method, the method does not get implemented.

This is due to the way templates are implemented. They are not implemented as generic methods that work for any type, they are implemented as specific methods for the types identified.

If you had a tree with two different argument types (say IntBinaryTree<foo> and IntBinaryTree<goo>) there must be an insert node defined for each...(IntBinaryTree<foo>::insertNode() and IntBinaryTree<goo>::insertNode()) they will not find or use a 'generic' insertNode().

(It is possible to have the template derive from an actual base class if there are methods that can actually operate without the type, and the implementation for the base class methods would be 'hidden' in a cpp file and linked to the code.

[mrnutty]

Put the definition in the same file as the templete header, unless your
compiler supports the keyword export.

[ncwolfe]

Oh my gosh, that it's it! Thanks a lot! When I re-read the section of my textbook on templates, I did not see any explicit declaration to that effect, so thanks a bunch for cluing me in. Now that you've explained it, the reasoning makes perfect sense.

[ncwolfe]

Thanks for the tip. Visual Studio 2005 does not support export.