I am coding a hash tree in C++, where I need two different types of nodes i.e. one for non leaf that will simply point to its children and other for leaf node which contains the required information.
The problem I am facing is that how can I declare pointers in non leaf node. Because some non leaf nodes are to point other non leaf nodes and some have to point the leaf nodes. So I cant declare one pointer type to the pointer in non leaf node.
Any help would be appreciated.
Rather than having a leaf node and a none leaf node, you could just have one node class with a data pointer. If the node is not a leaf node, then the data pointer will be NULL. If the node is a leaf node then the Node* will be NULL.
struct Node
{
Node *child; // NULL if leaf node
Data *data; // NULL if not leaf node
};
I would approach this with a union and a flag in the header that told me whether the pointer in question was pointing to a node or a leaf.
struct Header
{
int isLeaf;
}
struct Leaf
{
struct Header header;
struct LeafBody body;
}
struct Node
{
struct Header header;
struct NodeBody body;
}
union Entity
{
struct Header header;
struct Node node;
struct Leaf leaf;
}
There are several solutions to this. You could simply make a nonleaf inherit from the leaf, and let polymorphism handle it. Or use a union and a flag to determine which one to use. Or dirtiest of all, but sometimes valid, is a simple void* which you can always cast back to whatever you need. Depending on your specific needs: the union will perform best, the polymorphism will be most readable, and void* would be same performance as union and depending on taste a tad cleaner code if you dislike unions.
