Well, I tried looking through the net for a solution but I couldn't find anything that fixed my problem.
I am writing an assignment for class that has us make a binary tree search using templates. I had already built an integer binary search tree in a previous class, so this is mostly that same program with a few tweaks (the most significant being templates). The program as made in the previous class turned out working perfectly fine, but after applying the templates, it gives me a very strange set of errors:
1>tester.obj : error LNK2019: unresolved external symbol "public: __thiscall binTree<int>::~binTree<int>(void)" (??1?$binTree@H@@QAE@XZ) referenced in function _main
1>tester.obj : error LNK2019: unresolved external symbol "public: void __thiscall binTree<int>::deleteNode(int const &)" (?deleteNode@?$binTree@H@@QAEXABH@Z) referenced in function _main
1>tester.obj : error LNK2019: unresolved external symbol "public: bool __thiscall binTree<int>::find(int const &)" (?find@?$binTree@H@@QAE_NABH@Z) referenced in function _main
1>tester.obj : error LNK2019: unresolved external symbol "public: int __thiscall binTree<int>::height(void)" (?height@?$binTree@H@@QAEHXZ) referenced in function _main
1>tester.obj : error LNK2019: unresolved external symbol "public: void __thiscall binTree<int>::postorderTraversal(void)" (?postorderTraversal@?$binTree@H@@QAEXXZ) referenced in function _main
1>tester.obj : error LNK2019: unresolved external symbol "public: void __thiscall binTree<int>::preorderTraversal(void)" (?preorderTraversal@?$binTree@H@@QAEXXZ) referenced in function _main
1>tester.obj : error LNK2019: unresolved external symbol "public: void __thiscall binTree<int>::inorderTraversal(void)" (?inorderTraversal@?$binTree@H@@QAEXXZ) referenced in function _main
1>tester.obj : error LNK2019: unresolved external symbol "public: void __thiscall binTree<int>::insert(int const &)" (?insert@?$binTree@H@@QAEXABH@Z) referenced in function _main
1>tester.obj : error LNK2019: unresolved external symbol "public: __thiscall binTree<int>::binTree<int>(void)" (??0?$binTree@H@@QAE@XZ) referenced in function _main
My code is broken up between the header of the BTS class, a cpp file with the functions, and a cpp tester.
BinTree.h :
#pragma once
#include <iostream>
#include <string>
using namespace std;
//***** FUNCTION DESCRIBED BRIEFLY IN CPP FILE
template<class T>
class binTree
{
//the node struct
struct btnode {
T info;
btnode* left;
btnode* right;
};
private:
btnode* root; //the root
void remove(btnode* &node);
int heightRecursive(btnode *node);
void destroyRecursive(btnode*);
bool leaf(btnode* node) const;
// recursive traversals
void inorderRecursive(btnode* node);
void preorderRecursive(btnode* node);
void postorderRecursive(btnode* node);
public:
binTree(void);
int height();
void insert(const T &inData);
bool find (const T &inData);
void deleteNode(const T &inData);
~binTree(void);
// traversal
void inorderTraversal();
void preorderTraversal();
void postorderTraversal();
};
BinTree.cpp :
#include "BinTree.h"
//constructor, sets the root equal to NULL
template<class T> binTree<T>::binTree(void)
{
root = NULL;
}
//inserts into the tree; if the tree is empty, it inserts to the root
// if the tree already has the variable, it outputs a message and exits
// other wise, it will search for an appropiate place to fit the variable in
template<class T> void binTree<T>::insert(const T &inData)
{
btnode *newnode, *current, *parentOfCurrent;
newnode = new btnode;
newnode->info = inData;
newnode->left = newnode->right = NULL;
if (root == NULL) {
root = newnode;
cout << "added to root\n";
return; }
current = root;
while(current != NULL) {
parentOfCurrent = current;
if(current->info == inData)
{
cout << inData << " already exists in tree. Duplicates not allowed!\n";
return;
}
else if(current->info > inData)
current = current->left;
else
current = current->right;
}
if (parentOfCurrent->info > inData)
parentOfCurrent->left = newnode;
else
parentOfCurrent->right = newnode;
}
//--------------- inorder traversal ----------------------
//calls the inorderTraversal using the root
template <class T> void binTree<T>::inorderTraversal()
{
if(root==NULL)
cout << "Empty tree\n";
else {
inorderRecursive(root);
cout << '\n';
}
}
//Private variable, travels recursively in inorder accross the tree, takes in a btnode pointer
template <class T> void binTree<T>::inorderRecursive(btnode* node) //left, node, right
{
if(node != NULL) {
inorderRecursive(node->left);
cout << node->info << ", ";
inorderRecursive(node->right);
}
}
//------------------ preorder traversal-------------
//calls the preOrderTraversal using the root
template <class T> void binTree<T>::preorderTraversal()
{
if(root==NULL)
cout << "Empty tree\n";
else {
preorderRecursive(root);
cout << '\n';
}
}
//Private variable, travels recursively in preorder accross the tree, takes in a btnode pointer
template <class T> void binTree<T>::preorderRecursive(btnode* node) //node, left, right
{
if(node != NULL) {
cout << node->info << ", ";
preorderRecursive(node->left);
preorderRecursive(node->right);
}
}
//------------ postorder traversal-----------------
//calls the postOrderTraversal using the root
template <class T> void binTree<T>::postorderTraversal()
{
if(root==NULL)
cout << "Empty tree\n";
else {
postorderRecursive(root);
cout << '\n';
}
}
//Private variable, travels recursively in postorder accross the tree, takes in a btnode pointer
template <class T> void binTree<T>::postorderRecursive(btnode* node)
{
if(node != NULL) {
postorderRecursive(node->left);
postorderRecursive(node->right);
cout << node->info << ", ";
}
}
//-------
//searches the tree and returns either true or false if found or not found
template<class T> bool binTree<T>::find(const T &inData)
{
bool rv = false;
btnode *current;
if(root == NULL)
return rv;
current = root;
while(current != NULL && rv == false)
{
if (current->info == inData)
rv = true;
else if (current->info > inData)
current = current->left;
else
current = current->right;
}
return rv;
}
//deletes a node using the remove function. If the tree is empty or the variable
// is not found, it will send a message and abort.
template <class T> void binTree<T>::deleteNode(const T &inData)
{
btnode *current, *parentOfCurrent;
bool found = false;
if (root == NULL) {
cout << "The tree is empty, aborting...";
return;
}
current = root;
while(current != NULL)
{
if(current->info == inData) {
found = true;
break;
}
else {
parentOfCurrent = current;
if(current->info > inData)
current = current->left;
else
current = current->right;
}
}
if(!found)
cout << "\n" <<inData << " could not be found. Aborting...\n";
else if (current == root)
remove(root);
else if (parentOfCurrent->info > inData)
remove(parentOfCurrent->left);
else
remove(parentOfCurrent->right);
}
//
template <class T> void binTree<T>::remove(btnode* &node) // parent's node with address of
//node to be deleted. Sent in by ref. So parent's node changed here
{
btnode *current, *parentOfCurrent, *temp;
if(node==NULL) {
cout << "\nCannot delete NULL node.\n";
return; //the return is here because if the node is NULL, then it is also technically a leaf
}
else if(leaf(node) == true) //node is a leaf
{
temp = node;
node = NULL;
delete temp;
}
else
cout << "\nNode is not a leaf, cannot delete.\n";
}
//finds the height of the tree by passing root into the heightRecursive function
template <class T> int binTree<T>::height()
{
return heightRecursive(root);
}
//recursively travels the tree and keeps a counter each time it encounters a node
template <class T> int binTree<T>::heightRecursive(btnode* node)
{
if (node == NULL)
return 0;
else
return ( 1 + max(heightRecursive(node->left), heightRecursive(node->right)));
}
//destryuuctor; it calls the destroyRecursive function using root
template <class T> binTree<T>::~binTree(void)
{
destroyRecursive(root);
}
//travels the tree recursively, deleting every non-Null it encounters
template <class T> void binTree<T>::destroyRecursive(btnode* node)
{
if(node != NULL) {
destroyRecursive(node->left);
destroyRecursive(node->right);
delete node;
node = NULL;
}
}
//checks if the node passed as an argument is a leaf, returns true or false
template <class T> bool binTree<T>::leaf(btnode* node) const
{
bool aLeaf = false;
if(node->left == NULL && node->right == NULL)
aLeaf = true;
return aLeaf;
}
tester.cpp :
#include "BinTree.h"
int main()
{
binTree<int> example;
int arr[] = { 75,43,77,29,52,82,35,56,79,32,40,90,48,47 };
//inserts the array of integers into the tree
for(int i=0; i < 14; i++)
example.insert(arr[i]);
//---------------Displays tree before changes-------------------
cout << "In order traversal:\n";
example.inorderTraversal();
cout << "Pre-order traversal:\n";
example.preorderTraversal();
cout << "Post-order traversal:\n";
example.postorderTraversal();
cout << "------------------Displays tree after changes---------------------\n";
example.insert(21);
cout << "\n------- inorder --------\n";
example.inorderTraversal();
cout << "\n------- preorder --------\n";
example.preorderTraversal();
cout << "\n------- postorder --------\n";
example.postorderTraversal();
cout << "\nheight=" << example.height() << endl<<endl;
//tests the find function
if (example.find(9))
cout << "found 9\n";
else
cout << "9 not found\n";
if (example.find(77))
cout << "found 77\n";
else
cout << "77 not found\n";
//tests the delete function by trying to delete an integer not in the tree
example.deleteNode(122);
//test the insert by inserting already existent integer
example.insert(77);
//tests the delete function by deleting 77
example.deleteNode(77);
cout << "\nAfter deleting 77 (inorder)\n";
example.inorderTraversal();
system("pause"); //don't worry, the system call will be gone in the final submission
return 0;
}
As I said before, I'm fairly sure it has to do with something I did wrong with the template implementation. If it is templates, can I get the exact code fragment and what should be implemented? I am fairly new to templates, so it's making my head hurt a bit. If it helps, I use Visual Studios 2010.
Here you have why it won't work: Splitting templated C++ classes into .hpp/.cpp files--is it possible?
TL;DR: you cannot split template class between .h and .cpp files, move implementation to .h file.