Debugging the Constructor of a Binary Tree Class

[pandaman]

I am incrementally implementing a binary tree class and so far I have only the constructor

Here is my header file (named binary_tree.h):
---------------------------------------------------------------------------------
#ifndef MY_BINARYTREE_XXX
#define MY_BINARY_TREE_XXX
#include <cstdlib>

namespace my_binary_tree
{
template <class Item>
class binary_node
{
public:
//Typedefs and Constants
typedef Item value_type;
//Constructor
binary_node(const Item& init_data);
//Constant Member Functions

private:
Item data_field;
Item *left_branch;
Item *right_branch;
};
}
#include "binary_tree.cpp"
#endif
---------------------------------------------------------------------------------

And here is my implementation file (named binary_tree.cpp):
---------------------------------------------------------------------------------
namespace my_binary_tree
{

template <class Item>
binary_node<Item>::binary_node(const Item& init_data)
{
data_field = init_data;
left_branch = NULL;
right_branch = NULL;
}

}
---------------------------------------------------------------------------------

The error message I get when I compile with the command:
"g++ -c binary_tree.h binary_tree.cpp"
is
"binary_tree.cpp:5: error: expected constructor, destructor, or type conversion before '<' token. "

Line 5 of the binary_tree.cpp file is:
"binary_node<Item>::binary_node(const Item& init_data)"

How can I resolve this issue?

[Peter87]

The problem is when you try to compile binary_tree.cpp. The binary_node class has not been defined when you try to define the binary_node constructor.

[Lowest0ne]

A template function needs to be in the header. I would recommend making a tree that can only hold a primitive data type first (like int), and then try to template it later.

Your node needs node pointers, not Item pointers: binary_node<Item> *left_branch;

[pandaman]

After taking into consideration the helpful advice of you two, my code compiles into a .o.

I do have another issue, though. I created a driver to test whether the constructor works. It looks like this:
--------------------------------------------------------------------------------------------------
#include "binary_tree.h"
using namespace std;
using namespace my_binary_tree; //the namespace where binary_tree.h lives
int main()
{
binary_node<int> blah(4);
return 0;
}
--------------------------------------------------------------------------------------------------

When I compile the driver with the command:
"g++ -o driver binary_tree.h binary_tree.o driver.cpp"
I get a linking error.

When I remove the "using namespace my_binary_tree;" line from my driver code (because i'm not sure whether that namespace comes along with the include "binary_tree.h"), I get these errors:
driver.cpp:5: error: binary node was not declared in this scope
driver.cpp:5: error: expected primary expression before 'int'
driver.cpp:5: error: expected ';' before 'int'

[Lowest0ne]

If the .o is made then you don't need the .h in the command line.

I think you may want to reconsider the way your implementing this. I would suggest something along the lines of:

class binary_node
{
  // yada yada yada
  // no member functions needed
}

class binary_tree
{
private:
  binary_node* root;

// member functions here
}

A node doesn't have to know anything other than the data it stores. The tree doesn't know anything about the data, it just keeps things organized.

I know this link is for Linked-Lists but I found it very helpful:
http://www.stanford.edu/class/cs107l/handouts/04-Custom-Iterators.pdf

Edit: A tree probably doesn't have an iterator, but the general construct of a template container is there.