LNK2019: unresolved external symbol public

Question

I'm trying to write my code in Visual Studio 2013 for second time in CodeBlocks, I am getting an error while trying to arrange a Binary Search Tree, here is my code for BinarySearchTree.h

#pragma once
template <typename T>
class BinarySearchTree{
private:
    struct Node{
        Node *left;
        Node *right;
        T data;
    };
    Node *root;
public:
    BinarySearchTree();
    bool isEmptyTree() const;
    void insertInBinarySearchTree(T& value);
    void removeFromBinarySearchTree(T& value);
    void printBinarySearchTree();
    void inorderBinarySearchTree(Node *p);
};

Here is BinarySearchTree:

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

template <typename T>
BinarySearchTree<T>::BinarySearchTree(){
    root = nullptr;
}

template <typename T>
void BinarySearchTree<T>::insertInBinarySearchTree(T& value){
    Node *t = new Node;
    Node *parent;
    t->data = value;
    t->left = nullptr;
    t->right = nullptr;
    parent = nullptr;
    if (isEmptyTree()) root = t;
    else{
        Node *currentNode;
        currentNode = root;
        while (currentNode){
            parent = currentNode;
            if (t->data, currentNode->data) currentNode = currentNode->right;
            else currentNode = currentNode->left;
        }
        if (t->data < parent->data) parent->left = t;
        else parent->right = t;
    }
}
template <typename T>
void BinarySearchTree<T>::removeFromBinarySearchTree(T& value){
    bool isElementFound = false;
    if (isEmptyTree()){
        cout << "This tree is empty!" << endl;
        return;
    }
    Node *currentNode;
    Node *parent;
    currentNode = parent;
    while (currentNode != nullptr){
        if (currentNode->data == value){
            isElementFound = true;
            break;
        }
        else{
            parent = currentNode;
            if (value > currentNode->data) currentNode = currentNode->right;
            else currentNode = currentNode->left;
        }
    }
    if (!isElementFound()){
        cout << "Data not found in tree!" << endl;
        return;
    }
    if ((currentNode->left == nullptr && currentNode->right != nullptr) || (currentNode->left != nullptr && currentNode->right == nullptr)){
        if (currentNode->left = nullptr && currentNode->right != nullptr){
            if (parent->left == currentNode){
                parent->left = currentNode->right;
                delete currentNode;
            }
            else{
                parent->right = currentNode->right;
                delete currentNode;
            }
        }
        else{
            if (parent->left == currentNode){
                parent->left = currentNode->left;
                delete currentNode;
            }
            else{
                parent->right = currentNode->left;
                delete currentNode;
            }
        }
        return;
    }

    if (currentNode->left == nullptr && current->right == nullptr){
        if (parent->left == currentNode) parent->left == nullptr;
        else parent->right == nullptr;
        delete currentNode;
        return;
    }
    if (currentNode->left == nullptr && currentNode->right == nullptr){
        Node *checker;
        checker = currentNode->right;
        if ((checker->left == nulptr) && (checker->right == nullptr)){
            currentNode = checker;
            delete checker;
            currentNode->right = nullptr;
        }
        else{
            if ((currentNode->right)->left != nullptr){
                Node *leftCurrentNode;
                Node *leftCurrentNodeParent;
                leftCurrentNodeParent = currentNode->right;
                leftCurrentNode = (currentNode->right)->left;
                while (leftCurrentNode->left != nullptr){
                    leftCurrentNode = leftCurrentNodeParent;
                    leftCurrentNode = leftCurrentNode->left;
                }
                currentNode->data = leftCurrentNode->data;
                delete leftCurrentNode;
                leftCurrentNodeParent->left = nullptr;
            }
            else{
                Node *temporaryNode;
                temporaryNode = currentNode->right;
                currentNode->data = temporaryNode->data;
                currentNode->right = temporaryNode->right;
                delete temporaryNode;
            }
        }
        return;
    }
}
template <typename T>
void BinarySearchTree<T>::printBinarySearchTree(){
    inorderBinarySearchTree(root);
}
template <typename T>
void BinarySearchTree<T>::inorderBinarySearchTree(Node *p){
    if (p != nullptr){
        if (p->left) inorderBinarySearchTree(p->left);
        cout << " " << p->data << " ";
        if (p->right) inorderBinarySearchTree(p->right);
    }
    return;
}
template <typename T>
bool BinarySearchTree<T>::isEmptyTree() const{
    return root == nullptr;
}

And finally main.cpp:

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

int main()
{
    BinarySearchTree<int> BST;
    int ch, tmp, tmp1;
    while (1)
    {
        cout << endl << endl;
        cout << " Binary Search Tree Operations " << endl;
        cout << " ----------------------------- " << endl;
        cout << " 1. Insertion/Creation " << endl;
        cout << " 2. Removal " << endl;
        cout << " 3. Print " << endl;
        cout << " 4. Exit " << endl;
        cout << " Enter your choice : ";
        cin >> ch;
        switch (ch)
        {
        case 1: cout << " Enter Number to be inserted : ";
            cin >> tmp;
            BST.insertInBinarySearchTree(tmp);
            break;
        case 2: cout << " Enter data to be deleted : ";
            cin >> tmp1;
            BST.removeFromBinarySearchTree(tmp1);
            break;
        case 3: cout << endl;
            cout << " Print tree " << endl;
            cout << " -------------------" << endl;
            BST.printBinarySearchTree();
            break;
        case 4:
            return 0;
        }
    }
}

I found this error to be responsible for missing implementation, but I can't find function without implementation.

What exactly is the error that you are getting? It's hard to help without it. — Nicholas Pipitone, Oct 11 '15 at 16:00

score 0 · Answer 1 · answered Oct 11 '15 at 16:16

You need to implement the functions in the header file

"The only portable way of using templates at the moment is to implement them in header files by using inline functions."

https://books.google.co.il/books?id=n9VEG2Gp5pkC&pg=PA10&lpg=PA10&dq=%22The+only+portable+way+of+using+templates+at+the+moment+is+to+implement+them+in+header+files+by+using+inline+functions.%22&source=bl&ots=Ref8pl8dPX&sig=t4K5gvxtBblpcujNxodpwMfei8I&hl=en&ei=qkR6TvbiGojE0AHq4IzqAg&sa=X&oi=book_result&ct=result#v=onepage&q=%22The%20only%20portable%20way%20of%20using%20templates%20at%20the%20moment%20is%20to%20implement%20them%20in%20header%20files%20by%20using%20inline%20functions.%22&f=false

Nicholas Pipitone · Answer 2 · 2015-11-28T21:58:45.503

The problem you have is that in main.cpp, you instantiated your class using int as the template, so in the header file everything is treated as int. E.g. void insertInBinarySearchTree( int& value );

However, in the implementation file, the functions are still defined using the more general template definition, and on compile-time main.cpp is going to be looking for a function definition for

void insertInBinarySearchTree( int& value );

where it fails because in the cpp file you only have

void insertInBinarySearchTree( T& value );.

In order to fix this, simply go to the very last line of your cpp and add the following:

template class BinarySearchTree<int>;

And the problem will be fixed as a definition has been added that takes care of ints.

P.S: Looking through your code, it looks like = and == were being used incorrectly. Remember that = is for assignment and == is for checking whether two values are the same. There were many others errors as well, so I fixed the ones that I noticed here.

LNK2019: unresolved external symbol public

2 Answers2