Templates + ref to pointer + linker error.

header/cpp file combined in .h file since using templates:

Code:

template <class Entry>
struct Binary_node
{
	Entry data;
	Binary_node<Entry> *left;
	Binary_node<Entry> *right;
	Binary_node(); //constructors
	Binary_node(const Entry &x);
};

template <class Entry>
class Binary_tree
{
public:
	Binary_tree();
	void insert(const Entry &);
private:
	Binary_node<Entry> *root;
	void recursive_insert (Binary_node<Entry> *&sub_root, const Entry &data);
};

template <class Entry>
Binary_node<Entry>::Binary_node()
{left=right=NULL;}

template <class Entry>
Binary_tree<Entry>::Binary_tree()
{
	this->root=NULL;
}

template <class Entry>
void Binary_tree<Entry>::insert(const Entry &data)
{
	recursive_insert(root,data);
}

template <class Entry>
void Binary_tree<Entry>::recursive_insert(Binary_node<Entry> *&sub_root, const Entry &data)
{
	if (sub_root==NULL)
		sub_root=new Binary_node<Entry>(data);
	else
		if (data.key<sub_root->data.key)
			recursive_insert(sub_root->left,data);
		else
			recursive_insert(sub_root->right,data);
}

Main:

Code:

struct datanode
{
	int key;
	float gpa;
};

int main ()
{
	Binary_tree<datanode> tree;
	datanode data;

	data.key=89;
	data.gpa=3.3;

	tree.insert(data);
}

Getting this linker error:

error LNK2019: unresolved external symbol "public: __thiscall Binary_node<struct datanode>::Binary_node<struct datanode>(struct datanode const &)" (??0?$Binary_node@Udatanode@@@@QAE@ABUdatanode@@@Z ) referenced in function "private: void __thiscall Binary_tree<struct datanode>::recursive_insert(struct Binary_node<struct datanode> * &,struct datanode const &)" (?recursive_insert@?$Binary_tree@Udatanode@@@@AAEX AAPAU?$Binary_node@Udatanode@@@@ABUdatanode@@@Z)

[edit] - Sorry copied the wrong main, corrected... linker error is for the current one.

You've never defined

Code:

    Binary_node(const Entry & x);

Code:

struct Binary_node
{
	Entry data;
	Binary_node<Entry> *left;
	Binary_node<Entry> *right;
	Binary_node(); //constructors
	Binary_node(const Entry &x); // Where is the implementation?
};

Got it but now I've got another error, here's the implementation:

Code:

template <class Entry>
Binary_node<Entry>::Binary_node(const Entry &x)
{
	left=right=x;
}

error C2440: '=' : cannot convert from 'const datanode' to 'Binary_node<Entry> *'

Not sure, but I thought "const Entry &x" passes a reference to x to the Binary_node constructor so I should be able to equate left and right to it... no ?

Originally Posted by Sparrowhawk

Not sure, but I thought "const Entry &x" passes a reference to x to the Binary_node constructor so I should be able to equate left and right to it... no ?

But left and right are pointers, not Binary_node objects or references. Anyway, it looks like you should initialise those member pointers to be null pointers instead. What you should do with x is to use it to initialise the data member variable.

Originally Posted by laserlight

But left and right are pointers, not Binary_node objects or references. Anyway, it looks like you should initialise those member pointers to be null pointers instead. What you should do with x is to use it to initialise the data member variable.

I suppose that makes a lot more sense.

Question... Is the only difference between preorder and inorder traversal of a BT, that in preorder you want to hit the root first then everything else in order? where inorder is everything is inorder including the root?

Originally Posted by Sparrowhawk

I suppose that makes a lot more sense.

Question... Is the only difference between preorder and inorder traversal of a BT, that in preorder you want to hit the root first then everything else in order? where inorder is everything is inorder including the root?

I'm not sure I'd call that the "only" difference (in the sense of a small difference) but yes.

In-order:

process_left();
process_root();
process_right();

Pre-order:

process_root();
process_left();
process_right();

Post-order:

process_left();
process_right();
process_root();

Note that in all three cases, left is processed before right, so there are another 3 twins of these sequences with left/right swapped. Those don't have names, as far as I can tell.

Ok adding onto this... I want to do a fill tree function that takes an input file and reads in keys and gpas from it. But datanode (which defines the struct with keys/gpas) is in my main and this function is a member function of my bintree class.

How can I do this? and with templates..?


[edit] - Humm I got it, hope this isn't meant to be polymorphic... heh

Sparrowhawk - I saw you mention that you solved your first problem, but didn't see how you resolved it. Could you explain what the issue was? Was it because you needed to either 1) typedef your struct, or 2) declare the tree as:
Binary_tree<struct datanode> tree;

Thanks