Expert: vijayan - 8/24/2009

Question
I have designed a templated class about a binary tree which includes a friend functions.But it calls problems when the code are compiling . The problem is "undefined reference to PreOrderCreate(BiTree<char>)". The code is below:

#ifndef BITREE
#define BITREE
#include<iostream>
using namespace std ;
template<class T>
class BiTree
{
   private:
   class BiTreeNode
   {
       public:
       T val ;
       BiTreeNode* lchild ,* rchild ;
   } ;
   typedef BiTreeNode* BiTreePtr ;
   BiTreePtr root ;
   void DeleteTree(BiTreePtr root);
   
   public:
   BiTree() ;
   BiTree(BiTree<T>& LT , T& value , BiTree<T>& RT) ;
   
   bool IsEmpty() ;
   
   BiTree<T> LeftSubtree();
   
   BiTree<T> RightSubtree();
  
   T RootData() ;
 
   ~BiTree() ;
   
   friend void PreOrderCreate(BiTree<T> bt);


} ;
template<class T>
void PreOrderCreate(BiTree<T> bt)
{
   char temp ;
   cin >> temp ;
   bt.root->val = temp ;
   if((temp>='A'&&temp<='Z')||('a'<=temp&&temp<='z'))
   {
       bt.root->lchild = NULL ;
       bt.root->rchild = NULL ;
   }
   else
   {
       PreOrderCreate(bt.LeftChild) ;
       PreOrderCreate(bt.RightChild) ;
   }
}
//definitions of other functions
#endif

Answer
when the compiler sees the friend declaration in class definition

friend void PreOrderCreate(BiTree<T> bt);

it does not know the friend function is itself a template; it assumes it is a non-template function.
(Like this, when T is an int: void PreOrderCreate(BiTree<int> bt);)
When you call the PreOrderCreate() function, this assumption causes the compiler to generate a call to the non-template function, but the linker will give you an "undefined external" error because you never actually defined the non-template function.
You need to tell the compiler while it is examining the class body that the friend function is itself a  template.


One simple solution is: declare each template friend function before the definition of template class.
 
template<class T>
void PreOrderCreate(BiTree<T> bt) ;

template<class T>
class BiTree
{
    // ...

    friend void PreOrderCreate(BiTree<T> bt);
} ;



Another way is to add <> in the friend declaration lines, as below:

template<class T>
class BiTree
{
    // ...

    friend void PreOrderCreate <> (BiTree<T> bt);
} ;
This lets the compiler know that the friend is itself a template.



Yet another way is to define the friend inline inside the class definition:

template<class T>
class BiTree
{
    // ...

    friend inline void PreOrderCreate(BiTree<T> bt)
    {
       // ...
    }
} ;


Also, I think you need to pass the argument to PreOrderCreate() by reference.