Combining two separate ADTs into one

Hey guys I'm trying to get started on my CS assignment (second year C paper).

In this course we have created a Binary Search Tree ADT and also a Red Black Tree ADT. We have to combine them into one more general "Tree" ADT which will either choose to be a Red Black Tree or A Binary Search Tree depending on user input.

I have started by defining a new enumerated type; treetype_t which can either be set to RBT or BST... my first question is how do I declare the stru开发者_高级运维ct since I don't know which ADT will be selected? e.g. in my bst.c file I have:

struct bstnode {
   char *key;
   bst left;
   bst right;
};

and in my RBT file I have:

struct rbtnode {
   char *key;
   colour_t colour;
   rbt left;
   rbt right;
};

My first idea was to have an if statement such as

  if (treetype_t == RBT){
           struct rbtnode {
       char *key;
       colour_t colour;
       rbt left;
       rbt right;
    };
   }
     else{

         struct bstnode {
       char *key;
       bst left;
       bst right;
    };
}

However I don't think this will work... I can't think of another approach - any ideas?

Structure definitions can't be changed at run-time as in your code. You can only change them at compile time using the preprocessor's #if/#ifdef directive, but that's too early since at that moment you don't yet have the user input (unless the user can modify the source code directly and recompile it).

What you can do is combine those structures into one by using the union keyword:

struct rbtnode {
    char *key;
    colour_t colour;
    rbt left;
    rbt right;
};

struct bstnode {
    char *key;
    bst left;
    bst right;
};

union bst_or_rbt_node {
    struct bstnode bst_node;
    struct rbtnode rbt_node;
};

Then you use either the rbt_node member of the union or the bst_node member depending on the user input.

Make sure you allocate enough space for bst_or_rbt_node (safest would be using sizeof(bst_or_rbt_node)).

Also, I hope rbt and bst are pointer types.

It's not necessary to use unions, but at your current level it may be a little easier to deal with them than with pointers to e.g. void, pointer casts.