Inserting into a Binary Tree which uses void* in C

Question

I have to create a binary tree using the struct as follows:

struct treenode;
typedef struct treenode* TreeNode;
struct treenode {
 void* data;
 TreeNode left, right;
};

using void* as the type for the data to be stored at each leaf, so that an object of any type can be inserted into the tree.

When I am inserting a new leaf, I have to use a compare function, which checks if data in the new leaf is already in the tree, that takes two void* parameters eg:

int compare(void* a, void* b){
..
..
}

but how can I compare the two objects if I don't know what type they are?

Some code to solve this problem would be really helpful.

Answer 1

It won't be possible for you to compare the object data, as you only have a pointer to it and type or even size. The only thing you can do is check if the pointers are equal, which is as simple as a == b. Something like a->value == b->value would be undefined for void *, even if it was defined in the original function.

Answer 2

The comparison function is supposed to be supplied by the user of the tree, who knows what the actual type of the data is.

int compare(void const* va, void const* vb) {
    Foo const* a = va;
    Foo const* b = vb;
    ...
}

Answer 3

The best thing is to add a comparison function to the tree itself, but that will require you to maintain "a tree" as being something different than "a node in a tree", or duplicate the function in every node (which seems wasteful and weird):

typedef struct {
  TreeNode root;
  int (*compare)(const void *a, const void *b);
} Tree;

As Ioan pointed out in a comment, you can also let the insert() function deal with it:

TreeNode * tree_insert(TreeNode root, const void *data,
                       int (*compare)(const void *a, const void *b));

Note though that this is quite dangerous; you risk messing up the tree's structure if you pass different comparison-functions when inserting to the same tree.

Answer 4

If you really want to be able to store different types into each node, you're going to need an indicator in the node itself as to what type the payload is. Something like:

typedef enum {
    TYP_STRING,
    TYP_INT,
    TYPE_FLOAT
} tNodeType;
struct treenode {
    tNodeType typ;
    void* data;
    TreeNode left, right;
};

The your comparison function needs to first look at the type. If the types are different, the nodes are different. If the types are the same, you then need to compare the nodes based on the type. Off the top of my head so it may need debugging:

int compareNodes (TreeNode a, TreeNode b) {
    if (a->typ != b->typ) return FALSE;
    switch (a->typ) {
        case TYP_STRING: {
            return (strcmp ((char*)(a->data), (char*)(b->data)) == 0);
        }
        case TYP_INT: {
            return (*((int*)(a->data)) == *((int*)(b->data));
        }
        case TYP_FLOAT: {
            return (*((float*)(a->data)) == *((float*)(b->data));
        }
    }
    return FALSE;
}

If you don't need to store different types in the tree, then the type (and comparison function) belong to the tree rather than each node. This is the usual case although it is certainly possible to have a tree holding different types - it just makes the code mildly more complicated.

Answer 5

So, who are you in this case? Are you the one who implements the tree? Of are you the one who uses it? (You said your have to "create" the tree. But "create" is a rather ambiguous word.)

The one who implements the tree doesn't know and is not supposed to know the element type. That's the whole point. The three should be implemented so that it is completely independent of the actual type of the elements. This is why it uses void * pointers. And this is why it calls some external function to perform comparison.

The one who uses the three will, of course, know the actual type of the element. The user will supply actual elements, and the user will supply the appropriate comparison function. Since the user knows the actual type of his elements, they can cast the pointer type inside the comparison function from void * to the concrete pointer type an perform the actual comparison.

So, what are you supposed to be in this case? The user? Or the implementer?