Hey all - i am working on a implementation of a binary tree. I have all of my code and it is from an previous project for the most part. except a few changes ... i have to use a driver program for this that creates a tree, deletes the tree, increment/decrements data in the tree and then prints the tree.
My code i have 2 .h files, Node.h and BT.h. The node.h has the implementation of the Node class, which is related to BT.h as this is the actual binary tree class implementation file.
I have code that i am getting linker errors with... but i have the feeling that the error i am getting is unrelated to the code and the prototype as they are exactly the same pretty much and should word. The error section is with the bold part in my listed code:
BT.h file
#ifndef H_BT
#define H_BT
#include "340.h"
#include "Node.h"
template<class T> class BT {
public:
BT() { root = NULL; }
BT(const BT<T>&);
BT& operator=(const BT<T>&);
virtual ~BT() { clear(); }
bool empty() const { return root == 0; }
int size() const { return size(root); }
int height() const { return height(root); }
int leaves() const { return leaves(root); }
virtual void insert(const T& x) { insert(root, x); }
void clear() { clear(root); root = 0; }
void preOrder(void (*p)(T&)) { preOrder(root, p); }
void inOrder(void (*p)(T&)) { inOrder(root, p); }
void postOrder(void (*p)(T&)) { postOrder(root, p); }
protected:
Node<T>* root;
private:
int size(Node<T>*) const;
int height(Node<T>*) const;
int leaves(Node<T>*) const;
void insert(Node<T>*&, const T&);
void clear(Node<T>*);
void inOrder(Node<T>*, void (*)(T&));
void preOrder(Node<T>*, void (*)(T&));
void postOrder(Node<T>*, void (*)(T&));
Node<T>* copy(const Node<T>*);
};
template <class T>
BT<T>::BT(const BT<T> &treeCopy)
{
root = copy(treeCopy.root);
}
template <class T>
BT<T> & BT<T>::operator=(const BT<T> & rightOp)
{
if(this != &rightOp)
{
clear();
root = copy(rightOp.root);
}
return *this;
}
/****************************************************************
FUNCTION: size() RECURSIVE
ARGUMENTS: None
RETURNS: size of the tree
NOTES: this finds the size of the tree
****************************************************************/
template <class T>
int BT<T>::size(Node<T> * copyRoot) const
{
if (copyRoot == NULL)
return 0;
else
return 1 + (size(copyRoot->right) + size(copyRoot->left));
}
/****************************************************************
FUNCTION: height() RECURSIVE
ARGUMENTS: None
RETURNS: returns the size of the height
NOTES: this finds the height of the tree
****************************************************************/
template <class T>
int BT<T>::height(Node<T> * copyRoot) const
{
int leftSize = 0, rightSize = 0;
if (copyRoot == NULL)
return 0;
else
{
leftSize += height(copyRoot->left);
rightSize += height(copyRoot->right);
if (leftSize > rightSize)//if (height(copyRoot->left) > height(copyRoot->right))
return (1 + leftSize);
else
return (1 + rightSize);
}
}
[B]/****************************************************************
FUNCTION: height() RECURSIVE
ARGUMENTS: None
RETURNS: returns the size of the height
NOTES: this finds the height of the tree
****************************************************************/
template <class T>
int BT<T>::leaves(Node<T> * copyRoot) const
{
return 0;
}[/B]
/****************************************************************
FUNCTION: destroyTree()
ARGUMENTS: root of the tree
RETURNS: None
NOTES: this deletes the nodes of the tree
****************************************************************/
template <class T>
void BT<T>::clear(Node<T> * copyRoot)
{
if (copyRoot != NULL)
{
clear(copyRoot->left);
clear(copyRoot->right);
delete copyRoot;
}
}
/****************************************************************
FUNCTION: copy_tree()
ARGUMENTS: root of the tree
RETURNS: None
NOTES: this deletes the nodes of the tree
****************************************************************/
template <class T>
Node<T> * BT<T>::copy(const Node<T> * copyRoot)
{
if (copyRoot == NULL)
return NULL;
else
{
Node<T> * newNode;
newNode = new Node<T>(copyRoot->data);
newNode->left = copy(copyRoot->left);
newNode->right = copy(copyRoot->right);
return newNode;
}
}
/****************************************************************
FUNCTION: insert()
ARGUMENTS: data value
RETURNS: None
NOTES: inserts the new data item into the tree
****************************************************************/
template <class T>
void BT<T>::insert(Node<T>*& root, const T& newItem)
{
Node<T> * current = root, * parent = NULL;
while (current != NULL && newItem != current->data)
{
parent = current;
if (newItem < current->data)
current = current->left;
else // if (newItem > current->data)
current = current->right;
}
if (current != NULL)
return;
else
{
Node<T> * newNode;
newNode = new Node<T>(newItem);
if (parent == NULL)
root = newNode;
else
if (newNode->data < parent->data)
parent->left = newNode;
else
parent->right = newNode;
return;
}
}
/****************************************************************
FUNCTION: preTrav()
ARGUMENTS: root of the tree
RETURNS: None
NOTES: prints each member of the tree
****************************************************************/
template <class T>
void BT<T>::preOrder(Node<T> * current, void (*p)(T&))
{
if (current != NULL)
{
p(current->data);
preOrder(current->left, p);
preOrder(current->right, p);
}
}
/****************************************************************
FUNCTION: inTrav()
ARGUMENTS: root of the tree
RETURNS: None
NOTES: prints each member of the tree
****************************************************************/
template <class T>
void BT<T>::inOrder(Node<T> * current, void (*p)(T&))
{
if (current != NULL)
{
inOrder(current->left, p);
p(current->data);
inOrder(current->right,p);
}
}
/****************************************************************
FUNCTION: postTrav()
ARGUMENTS: root of the tree
RETURNS: None
NOTES: prints each member of the tree
****************************************************************/
template <class T>
void BT<T>::postOrder(Node<T> * current, void (*p)(T&))
{
if (current != NULL)
{
postOrder(current->left, p);
postOrder(current->right, p);
p(current->data);
}
}
#endif //END OF BS.HLinker errors given:
[Linker error] undefined reference to `BT<int>::leaves(Node<int>*) const'
[Linker error] undefined reference to `BT<float>::leaves(Node<float>*) const'
[Linker error] undefined reference to `BT<std::string>::leaves(Node<std::string>*) const'
This function obviously doesnt do anything of use ... but it should still function without any linker errors, at least to my knowledge, so the error has to be elsewhere!
Hope someone can see my mistake... i will post a section of the driver program given for reference to see how things are passed/called etc.
#include "BT.h"
#define Empty(x)\
cout << "tree is " << (x.empty() ? "" : "not ") << "empty\n"
#define HDR(x) Empty(x);\
cout << "\tno of nodes = " << setw(2) << x.size()\
<< "\n\tno of leaves = " << setw(2) << x.leaves()\
<< "\n\theight of tree = " << setw(2) << x.height()\
<< endl << endl;
#define ORD(x,y,s,t)\
cout << "The elements of '" << s << "' in " << t << ":\n\t";\
x.y(print_vals); cout << endl
template<class T>
void print_vals(T& x) { cout << x << ' '; }
...
...
const float b[] = { 0.5, 1.75, -3, 4.25, 5.50, -6.75, 8, 9.25,
-10.5 };
....
...
const int sz_b = sizeof(b) / sizeof(float);
...
BT<float> third, fourth;
for (int i = 0; i < sz_b; i++)
third.insert(b[i]);
cout << "third: "; HDR(third);
third.preOrder(increase_vals);
ORD(third, preOrder, "third", "preorder");
cout << endl;
fourth = third;
cout << "fourth: "; HDR(fourth);
fourth.postOrder(decrease_vals);
ORD(fourth, postOrder, "fourth", "postorder");
cout << endl;
return 0;
}Thank you in advance