I have a BinarySearchTree class and a BinaryNode class. My code is correct regarding its syntax. But on compiling, it generates linker errors. I only tried Visual Studio 2012's compilor and I want the same compilor to be use because my entire project is on VS2012. I wrote the code of classes and all the functions below and firstly, the errors as follows::
1>Source.obj : error LNK2019: unresolved external symbol "public: __thiscall BinarySearchTree::BinarySearchTree(int const &)" (??0?$BinarySearchTree@H@@QAE@ABH@Z) referenced in function _main
1>Source.obj : error LNK2019: unresolved external symbol "public: __thiscall BinarySearchTree::~BinarySearchTree(void)" (??1?$BinarySearchTree@H@@QAE@XZ) referenced in function _main
1>Source.obj : error LNK2019: unresolved external symbol "public: void __thiscall BinarySearchTree::insert(int const &)" (?insert@?$BinarySearchTree@H@@QAEXABH@Z) referenced in function _main
1>Source.obj : error LNK2019: unresolved external symbol "public: void __thiscall BinarySearchTree::remove(int const &)" (?remove@?$BinarySearchTree@H@@QAEXABH@Z) referenced in function _main
1>Source.obj : error LNK2019: unresolved external symbol "public: void __thiscall BinarySearchTree::printTree(void)const " (?printTree@?$BinarySearchTree@H@@QBEXXZ) referenced in function _main
1>c:\users\aftab electronics\documents\visual studio 2012\Projects\BST\Debug\BST.exe : fatal error LNK1120: 5 unresolved externals
//BinarySearchTree.h
#ifndef _BINARY_SEARCH_TREE_H
#define _BINARY_SEARCH_TREE_H
#include<iostream>
//Binary Node and Forward Declaration
template<class EType> class BinarySearchTree;
template<class EType> class BinaryNode{
EType element;
BinaryNode* left, *right;
public:
BinaryNode(const EType& theElement, BinaryNode* lt, BinaryNode *rt):element(theElement),left(lt),right(rt){}
friend class BinarySearchTree<EType>;
};
template<class EType> class BinarySearchTree{
public:
BinarySearchTree(const EType& notFound);
BinarySearchTree(const BinarySearchTree& rhs);
~BinarySearchTree();
const EType& findMin() const;
const EType& findMax() const;
const EType& find(const EType& x) const;
bool isEmpty() const;
void printInOrder() const;
void insert(const EType& x);
void remove(const EType& x);
void printTree() const;
void printTree(BinaryNode<EType>* ) const;
BinaryNode<EType>* clone(BinaryNode<EType> *t) const;
const BinarySearchTree& operator= (const BinarySearchTree& rhs);
private:
BinaryNode<EType>* root;
//ITEM_NOT_FOUND object used to signal failed finds
const EType ITEM_NOT_FOUND;
const EType& elementAt(BinaryNode<EType>* t) const;
void insert(const EType& x, BinaryNode<EType>* &t);
void remove(const EType& x, BinaryNode<EType>* &t);
BinaryNode<EType>* findMin(BinaryNode<EType>* t) const;
BinaryNode<EType>* findMax(BinaryNode<EType>* t) const;
BinaryNode<EType>* find(const EType& x, BinaryNode<EType>* t) const;
void makeEmpty(BinaryNode<EType>* &t);
void printInOrder(BinaryNode<EType>* t);
void makeEmpty();
};
#endif
And then, the implementation file BinarySearchTree.cpp is as below:
#include "BinarySearchTree.h"
#include<iostream>
//Construct The Tree
template<class EType> BinarySearchTree<EType>::BinarySearchTree(const EType& notFound):ITEM_NOT_FOUND(notFound), root(NULL){}
//Copy COnstructor
template<class EType> BinarySearchTree<EType>::BinarySearchTree(const BinarySearchTree<EType>& rhs):root(NULL),ITEM_NOT_FOUND(rhs.ITEM_NOT_FOUND)
{
*this = rhs;
}
//Destructor
template<class EType> BinarySearchTree<EType>::~BinarySearchTree(){makeEmpty();}
//Insert x into the Tree, Duplicates are iqnored
template<class EType> void BinarySearchTree<EType>::insert(const EType& x){insert(x, root);}
//Remove X from the Tree. Nothing is done if x is not found.
template<class EType> void BinarySearchTree<EType>::remove(const EType& x){remove(x, root);}
//Find the smallest item in the tree. Return it. Return ITEM_NOT_FOUND if empty
template<class EType> const EType& BinarySearchTree<EType>::findMin() const
{
return elementAt (findMin(root));
}
//Find largest item in tree. return or return ITEM_NOT_FOUND if empty
template<class EType> const EType& BinarySearchTree<EType>::findMax() const {
return elementAt(findMax(root));
}
//Find item x in the tree. return the matching or ITEM_NOT_FOUND if not exist
template<class EType> const EType& BinarySearchTree<EType>::find(const EType& x) const{
return elementAt(find(x,root));
}
//Make the tree logically empty
template<class EType> void BinarySearchTree<EType>::makeEmpty(){
makeEmpty(root);
}
//Test if the tree is logically empty. Return true otherwise false
template<class EType> bool BinarySearchTree<EType>::isEmpty() const{
return root == NULL;
}
//Print Tree in sorted order
template<class EType> void BinarySearchTree<EType>::printTree() const {
if (isEmpty())
cout<< "Empty Tree\n";
else
printTree(root);
}
//Deep Copy
template<class EType> const BinarySearchTree<EType>& BinarySearchTree<EType>::operator=(const BinarySearchTree<EType>& rhs){
if(this != &rhs){
makeEmpty();
root = clone(rhs.root);
}
return *this;
}
//Internal Method to get element in field in node t. Return the element field or ITEM_NOT_FOUND if t is NULL
template<class EType> const EType& BinarySearchTree<EType>::elementAt(BinaryNode<EType> *t) const {
if(t == NULL) return ITEM_NOT_FOUND;
else return t->element;
}
//internal method to insert into a subtree. x is to be inserted, t roots the tree.
template<class EType> void BinarySearchTree<EType>::insert(const EType& x, BinaryNode<EType>* &t) {
if(t==NULL)
t = new BinaryNode<EType>(x, NULL, NULL);
else if(x < t->element)
insert(x, t->left);
else if(t->left < x)
insert(x, t->right);
else
; // duplicate do nothing
}
//Internal method to remove from a subtree. x is the item to remove. t is the node that roots the tree.
template<class EType> void BinarySearchTree<EType>::remove(const EType& x, BinaryNode<EType>* &t) {
if(t == NULL) return; //Item not found, do nothing
if(x < t->element)
remove(x, t->left);
else if(t->element < x)
remove(x, t->right);
else if(t->left != NULL && t->right != NULL)
{
t->element = findMin(t->right)->element;
remove(t->element, t->right);
}
else {
BinaryNode<EType>* nodeToDelete = t;
t = (t->left != NULL) ? t->left : t->right;
delete nodeToDelete;
}
}
// Internal method to find the smallest item in a subtree t. return node containing the smallest item.
template<class EType> BinaryNode<EType>* BinarySearchTree<EType>::findMin(BinaryNode<EType>* t) const {
if(t == NULL) return NULL;
if(t->left == NULL) return t;
return findMin(t->left);
}
// Internal method to find the largest item in a subtree t. Return node containg the largest item.
template<class EType> BinaryNode<EType>* BinarySearchTree<EType>::findMax(BinaryNode<EType>* t) const{
if(t != NULL)
while(t->right != NULL)
t = t->right;
return t;
}
//Internal method to find an item in a subtree. x is searchee. t node roots the tree. return node containg match item
template<class EType> BinaryNode<EType>* BinarySearchTree<EType>::find(const EType& x, BinaryNode<EType> *t) const {
if(t == NULL) return NULL;
else if(x < t->element) return find(x, t->left);
else if(t->element < x) return find(x, t->right);
else return t; //Match
//// NON RECURSIVE VERSION ///
/*
while(t != NULL)
if(x < t->element)
t = t->left;
else if(t->element < x)
t = t->right;
else
return t; // Match
return NULL; //No Match
*/
}
//INternal method to make subtree empty
template<class EType> void BinarySearchTree<EType>::makeEmpty(BinaryNode<EType>* &t){
if(t != NULL){
makeEmpty(t->left);
makeEmpty(t->right);
delete t;
}
t = NULL;
}
//Internal method to print subtree rooted at t in sorted order
template<class EType> void BinarySearchTree<EType>::printTree(BinaryNode<EType>* t) const {
if(t != NULL){
printTree(t->left);
cout<<t->element<<endl;
printTree(t->right);
}
}
//Internal method to clone subtree
template<class EType> BinaryNode<EType>* BinarySearchTree<EType>::clone(BinaryNode<EType> *t) const{
if(t == NULL) return NULL;
else return new BinaryNode<EType>(t->element, clone(t->left), clone(t->right));
}
After it, the source.cpp file that contains main program is :
#include<iostream>
#include "BinarySearchTree.h"
int main(){
const int ITEM_NOT_FOUND = -9999;
BinarySearchTree<int> t(ITEM_NOT_FOUND);
int NUMS = 30;
int i;
std::cout<<"Inserting Elements (1 to 30) in the trees ..... )"<<std::endl;
for(i=0; i<=NUMS; i++)
t.insert(i);
std::cout<<"Printing the values of nodes in tree...."<<std::endl;
t.printTree();
std::cout<<"\n\nRemoving the even number elements in the tree ..........."<<std::endl;
for(i=0; i<=NUMS; i+=2)
t.remove(i);
std::cout<<"Printing the values of nodes in tree....."<<std::endl;
t.printTree();
system("pause");
}
please tell me how to resolve these linker errors.
