Archived

This topic is now archived and is closed to further replies.

binary tree template class question

This topic is 5667 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

ok, so lets say I have some binary tree function: template NODE * binarytree::insertNode(NODE * root,TYPE data) { if (root == NULL) //create node, blah blah //blah blah blah //a bunch of code goes here, irrelevent //here is the problem: else if (data > root->data) insertNode(root->right,data); //here is where I want to add my right node //but I have a problem } ok how do I compare the the data? Is this even possible? I can''t overload the > sign for every single data type. all template binary trees just write addLeftNode() functions and then you have to do it manually in your main. Thats no good, but is that the only way it can be done?

Share this post


Link to post
Share on other sites
Binary trees are defined by a right node being greater than its parent node and the left node being less than the parent node. So yes if you want to generalise this using a template then any type that you want to put into the template must overload the greater-than operator (and probably the less-than one aswell).

STL containers have these types of restrictions too. e.g. types used for the key in a map have to be comparable so that the elements can be kept sorted by key.

So its not unreasonable to require nodes of your binary tree to require the overloading of the greater-than operator.

Cheers,

Ryan.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
You can write and compare all the data types you want, simply writing a base class and deriving from that. The base class has a general "operator <" which returns a boolean (returns always false or true). With inheritance you return the right answer based on your real data type.

For example:

class BaseType
{
...
bool operator < (const BaseType &x) {return true;};
...
};

class TYPE : public BaseType // that''s _your_ "TYPE"
{
...
bool operator < (const BaseType &x)
{
TYPE *p=(TYPE*)&x;
/* <- here you compare members of ''this'' and ''p'' -> */
};
...
};

I hope this can help you.

Fil (il genio)

Share this post


Link to post
Share on other sites
quote:
Original post by Bloodshot Eye
Binary trees are defined by a right node being greater than its parent node and the left node being less than the parent node.


No, thats a binary search|sort tree. The term binary tree is any tree in which each node has 0-2 children. For example, a heap is a binary tree, but does not satisfy your definition.



Share this post


Link to post
Share on other sites