Insert Node into a Binary Search Tree using cpp

Question

I'm having trouble trying to insert nodes into my Binary Search Tree. I keep getting

error LNK2019: unresolved external symbol "public: __thiscall tree::tree(void)" (??0?$tree@H@@QAE@XZ)

Can someone tell me what the problem is please.

treenode.h

template <class T> class tree;

//treenode class-template definition
template <class T>
class treenode
{
friend class tree<T>;

public:

    treenode(const T &d, treenode<T> *l, treenode<T> *r)
        : data(d), leftptr(l), rightptr(r)
    {

    }

    treenode(const T &d):
        leftptr(0),
        data(d),
        rightptr(0)
    {

    }

    T getData() const
    {
        return data;
    }

private:
    treenode<T> *leftptr;
    T data;
    treenode<T> *rightptr;
};//end class treenode

tree.h

class tree
{
public:
    tree(); //initializes the private data member

    void insertNode (treenode<T> **, const T &);
    void preOrderTraversal(treenode<T> * ) const;
    void postOrderTraversal(treenode<T> * ) const;
    void inorderTraversal(treenode<T> *) const;

private:
    treenode<T> *rootptr;
};

tree.cpp

#include <iostream>
#include "tree.h"
using namespace std;

//constructor
template< class T>
tree<T>::tree()
{
rootptr = 0; //indicate tree is initially empty
}//end tree constructor


//insert node in tree
template <class T>
void tree<T>::insertNode(treenode<T> **rootptr, const T &val)
{
// subtree is empty; create new treenode containing value
if(*rootptr == 0)
    *rootptr = new treenode<T>(val);
else // subtree is not empty
{
    // data to insert is less than data in current node
    if(val < (*rootptr)->data)
    {
        insertNode(&((*rootptr)->leftptr), val);
    }
    else
    {
        // data to insert is greater than data in current node
        if(val > (*rootptr)->data)
        {
            insertNode(&((*rootptr)->rightptr), val);
        }
    }//end else
}//end else
}//end function insertNode

tester.cpp

int main()
{
   tree <int> create;
   int userVal;

   cout << "Enter 10 Integers" << "\n\n";
   for(int i=0; i<10; i++)
{
    cout << "-> ";
    cin >> userVal;
    createTree.insertNode(0, userVal);
    }

   system("pause");
   return 0;
}//end main

you're missing a `template ` before the class `tree` definition. I assume it's a simple omission in your question, but I'm signaling it just in case. — didierc, Apr 14 '13 at 23:29

score 0 · Answer 1 · edited May 23 '17 at 12:28

The problem is that the constructor for tree is not defined in the tree.h header file. The compiler needs the full definition of the template in order to instantiate it. Right now, what happens is that some file includes tree.h, and the compiler sees the class definition of the tree class but can't find a definition for its constructor.

So you need to move everything that is in the tree.cpp file into tree.h. (This doesn't apply to ordinary, non-template classes.)

It's actually slightly more complicated than that: Storing C++ template function definitions in a .CPP file

So you can get away with putting the definition in the .cpp file, but only if you explicitly instantiate the template for all the types you are going to use it with. The simplest solution is still to put the whole definition in the header file.

Insert Node into a Binary Search Tree using cpp

1 Answers1