Linking errors for my Binary Search Tree program

jamesdavis86 (2)
This is my first post, sort of, and I hope this is in the right section.

For homework, I am writing a program for a binary search tree. Now, whether the code is implemented correctly or not, it should at least compile. I am receiving this error, and no amount of googling is helping me. I can't seem to figure out the solutions to my problem. Apparently, this can be avoided by placing everything in the header file, but there has to be a cleaner solution.... right?

I've tried this on VS2010 and Dev C++, but I have the same errors... I hope you guys can help. Thank you in advance.

Note: I've deleted A LOT of comments in my code for this to fit the 8192-word limit, so sorry if the code doesn't speak for itself. The code itself compiles, so hopefully that's not the problem.

First the errors, which I'm pretty sure you guys have seen before:
1
2
3
4
 
Error	4	error LNK1120: 3 unresolved externals	C:\Users\Nemesis\Documents\Visual Studio 2010\Projects\Homework 2\Release\Homework 2.exe	Homework 2
Error	1	error LNK2001: unresolved external symbol "public: __thiscall BST<int>::~BST<int>(void)" (??1?$BST@H@@QAE@XZ)	C:\Users\Nemesis\Documents\Visual Studio 2010\Projects\Homework 2\Homework 2\main.obj	Homework 2
Error	3	error LNK2001: unresolved external symbol "public: __thiscall BST<int>::BST<int>(void)" (??0?$BST@H@@QAE@XZ)	C:\Users\Nemesis\Documents\Visual Studio 2010\Projects\Homework 2\Homework 2\main.obj	Homework 2
Error	2	error LNK2001: unresolved external symbol "public: virtual bool __thiscall BST<int>::insert(int)" (?insert@?$BST@H@@UAE_NH@Z)	C:\Users\Nemesis\Documents\Visual Studio 2010\Projects\Homework 2\Homework 2\main.obj	Homework 2


And the search tree *.cpp, *.h, and main.cpp: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
# ifndef BST_H
# define BST_H

#include <cstdlib>

template <typename Comparable> class BST;
template <typename Comparable> class Node;

template <typename Comparable>
class BST
{
protected:
    Node<Comparable> * head;
    int numberOfElements;
public:
    BST();
    virtual bool insert (Comparable data);
    virtual bool remove (Comparable data);
    // virtual so I can override these in an AVL implementation
    bool search (Comparable & data);
    ~BST();

    friend class Node <Comparable>;

private:
    bool remove (Comparable & data, Node<Comparable> * current);
    bool search (Comparable & data, Node<Comparable> * current);
    void deleteTree(Node<Comparable> * current);

};

template <typename Comparable>
class Node
{
public:
    Node<Comparable> * leftChild;
    Node<Comparable> * rightChild;
    Node<Comparable> * parent;

    Comparable data;

    Node(Comparable newData, Node * & parent);
    ~Node();
};

# endif 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
 
#include <cstdlib>
#include <iostream>
#include "BST.h"

template <typename Comparable>
BST<Comparable>::BST()
{
    head = 0;
    int numberOfElements = 0;
}

template <typename Comparable>
bool BST<Comparable>::insert (Comparable data)
{
    if (!head)
    {
        head = new Node<Comparable>(data, 0);
        return true;
    }

    Node<Comparable> * temp = head;

    while (temp)
    {
        if (data == temp -> data)
            return true;
        if (data < temp -> data)
            if (!(temp -> leftChild))
            {
                temp -> leftChild = new Node<Comparable> (data, temp);
                return true;
            }
            else
            {
                temp = temp -> leftChild;
                continue;
            }

        if (temp -> data < data)
            if (!(temp -> rightChild))
            {
                temp -> rightChild = new Node<Comparable> (data, temp);
                return true;
            }
            else
            {
                temp = temp -> rightChild;
                return true;
            }
    }

    // Insert fails if it reaches this point in a program, so return false
    return false;
} 

template <typename Comparable>
bool BST<Comparable>::remove (Comparable data)
{
    if (!head)
        return true;
    else remove(data, head);

}

template <typename Comparable>
bool BST<Comparable>::remove (Comparable & data, Node<Comparable> * current)
{
    if (!current)
        return true;
    if (data < current -> data)
        if (!(current -> leftChild))
            return true;
        else remove(data, current -> leftChild);
    if ((current -> data) < data)
        if (!(current -> rightChild))
            return true;
        else remove(data, current -> rightChild);
    if (data == current -> data)
    {
        // If the current node has no children
        if (!(current -> leftChild) && !(current -> rightChild))
        {
            //if current is not the root
            if (current -> parent)
            {
                if (current -> parent -> leftChild == current)
                // set pointers to child to null
                    current -> parent -> leftChild = 0;
                else current -> parent -> rightChild = 0;
                // delete entry and return true
                delete current;
                return true;
            }
            else // if current is the root
            {
                // remove the data
                delete current;
                // .. and set the BST's head pointer to null
                this -> head = 0;
                return true;
            }
        }
        // If the current node had one child
        if ((current -> leftChild && !(current -> rightChild)) 
        || (current -> rightChild && !(current -> leftChild)))
        {
            Node<Comparable> * childPTR;
            if (current -> leftChild)
                childPTR = current -> leftChild;
            else childPTR = current -> rightChild;

            if (this -> head == current)
            {
                this -> head = childPTR;
                childPTR -> parent = 0;
                delete current;
                return true;
            }
            else
            {
                if (current -> parent -> leftChild == current)
                    current -> parent -> leftChild = childPTR;
                else
                    current -> parent -> rightChild = childPTR;

                childPTR -> parent = current -> parent;
                delete current;
                return true;
            }
        }

        if ((current -> leftChild) && (current -> rightChild))
        {

            Node<Comparable> * nextNode = current -> rightChild;
            while (nextNode -> leftChild)
            {
                nextNode = nextNode -> leftChild;
            }

            current -> data = nextNode -> data;

            remove (nextNode -> data, nextNode);

            return true;
        }
    }
    return false;
}

template <typename Comparable>
bool BST<Comparable>::search (Comparable & data)
{
    if (!head)
        return false;
    else 
        search(data, head);

}

template <typename Comparable>
bool BST<Comparable>::search (Comparable & data, Node<Comparable> * current)
{

    if (!current)
        return false;
    if (data < current -> data)

        if (!(current -> leftChild))
            return false;
        else search(data, current -> leftChild);
    if ((current -> data) < data)
        if (!(current -> rightChild))
            return false;
        else search(data, current -> rightChild);
    if (data == current -> data)
        return true;

    std::cout << "End of search function reached in error. Please debug.\n";
    return false;
}

template <typename Comparable>
BST<Comparable>::~BST()
{
    if (!head)
        return;
    else
    {
        deleteTree(head);
        head = 0;
    }
}

template <typename Comparable>
void BST<Comparable>::deleteTree(Node<Comparable> * current)
{
    if (!current)
        return;
    if (current -> leftChild)
        deleteTree(current -> leftChild);
    if (current -> rightChild)
        deleteTree(current -> rightChild);

    delete current;
}

template <typename Comparable>
Node<Comparable>::Node(Comparable newData, Node * & parent)
{

    leftChild = 0;
    rightChild = 0;
    this -> parent = parent;

    data = newData;
}

template <typename Comparable>
Node<Comparable>::~Node()
{
    delete leftChild;
    delete rightChild;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
#include <cstdlib>
#include <iostream>
#include <string>
#include "BST.h"

int main()
{    
    BST<int> intTree;

    intTree.insert(3);
    intTree.insert(9);
    intTree.insert(7);
    intTree.insert(1);
    intTree.insert(3);
    intTree.insert(22);
    intTree.insert(-17);
    intTree.insert(8);
    intTree.insert(4);
    intTree.insert(2);

    return 0;
}
Last edited on
naraku9333 (2163)
From what I understand template classes MUST be declared AND implemented in the header. Whether you save it as .h or .cpp doesn't matter.
jamesdavis86 (2)
Your reply gave me something new to search for, and you are right... for the most part. The solution to my problem, apparently, is explicit instantiation. Though it's a good solution, I think it'll be less pain if I just place all of my class f(x) implementations in the header.

Thank you naraku!

Source: http://www.drdobbs.com/184403420;jsessionid=ZHRBF54UFNHMBQE1GHRSKHWATMY32JVN
Topic archived. No new replies allowed.