binary tree template class question
Author
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?
Why can''t you overload > for every type? This is what you have to do for sorting in the STL containers, and makes sense.
Helpful links:
How To Ask Questions The Smart Way | Google can help with your question | Search MSDN for help with standard C or Windows functions
Helpful links:
How To Ask Questions The Smart Way | Google can help with your question | Search MSDN for help with standard C or Windows functions
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.
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.
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)
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)
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
