binary tree: user decides whether it should be a number tree or a word tree in c programming

Question

in my assignment i have to create a binary tree where the user inputs the details.

the first thing the user does is enter 1 if they want to create a number tree or 2 if they want a word tree.

the type of tree they pick is the type it will be for the duration of the running of the program.

there are many functions (and a few structs) that must be written in order to complete the assignment.

my question is how can i write general functions that will work for both int and char?

for example if it is a number tree then the struct for node would include: int key; list_t* valueslist; node* left; node* right;

but if it was a word list than the struct would look the same except instead of int key it would be char key.

thanks in advance for any help!

Answer 1

The way you may go about it, is to define that data in the struct as a union like so:

struct _Node
{
  ...
  union
  {
    char* c;
    int i;
  } data;
};

Than when user makes the choice, access the correct union member according to it.

EDIT

So, let's say the user picked a type, int for instance. And you wish to insert a new value into the tree. (I'll omit error checking fro brevity, but remember to check memory allocation succeeded).

struct _Node* newElem = allocNode();

if (get_user_elected_type() == INT)
    newElem->data.i = user_input.i; // Your methods will also need to accept a union

This way has it's serious drawbacks (it's not easy to add a new type, for instance). And most of all it demonstrates how yucky generic programming can be in C. (Using void* can get just as yucky eventually).

Answer 2

There are few solutions to resolve this problem (what you are trying to do is called generic programming)

1. Use void * key, and fill it with the right data (this is recommended, because is more generic, but it is also more complicated)
2. Use a union with 2 fields: an int and a char*

Answer 3

For a homework assignment, the simpler approach will be to use a union type for your data:

struct node {
  union {
    char *s
    int   i;
  } data;
  struct node *left;
  struct node *right;
};

and create two sets of functions, one to manage integer values and the other to manage string values:

void insertIntNode(struct node *root, struct node *newNode)
{
  if (newNode->data.i < root->data.i)
    if (root->left != NULL)
      insertIntNode(root->left, newNode);
    else
      root->left = newNode;
  else
    if (root->right != NULL)
      insertIntNode(root->right, newNode);
    else
      root->right = newNode;
}

void insertWordNode(struct node *root, struct node *newNode)
{
  if (strcmp(root->data.s, newNode->data.s) < 0)
    if (root->left != NULL)
      insertWordNode(root->left, newNode);
    else
      root->left = newNode;
  else
    if (root->right != NULL)
      insertWordNode(root->right, newNode);
    else
      root->right = newNode;
  }

bearing in mind you'll need to do some additional memory management for word data:

struct node *createWordNode(char *str)
{
  struct node *r = malloc(sizeof *r);
  if (r)
  {
    r->data.s = malloc(strlen(str) + 1);
    if (r->s) 
      strcpy(r->data.s, str); 
    r->left = r->right = NULL;
  }
  return r;
}

void destroyWordNode(struct node **n)
{
  free((*n)->data.s);
  free(*n);
  *n = NULL;
}

A more flexible approach is to use a void * to point to your data item, and then delegate all type-aware operations (allocation, assignment, comparison, display, etc.) to other functions which are hidden behind a set of function pointers. For example:

struct node {
  void *data;
  struct node *left;
  struct node *right;
};

struct node *newNode(void *data, void *(*copy)(const void *))
{
  struct node *n = malloc(sizeof *n);
  if (n)
  {
    n->left = n->right = NULL;
    n->data = copy(data);
  }
  return n;
}

void insert(struct node *root, struct node *newNode, 
    int (*compare)(const void *, const void *))
{
  if (compare(newNode->data, root->data) < 0)
    if (root->left != NULL)
      insert(root->left, newNode, compare);
    else
      root->left = newNode;
  else
    if (root->right != NULL)
      insert(root->right, newNode);
    else
      root->right = newNode;
}

In the examples above, the details of allocating memory for a node's data element and comparing two data elements are delegated to other functions, and pointers to those functions are passed as parameters to the list management functions. This way you wind up writing a single newNode and insert function, but one that's capable of handling arbitrary node data types. So, for your integer tree, you'd write functions like

void *copyInt(const void *data)
{
  const int *src = data;
  int *dst = malloc(sizeof *dst);
  if (dst)
  {
    *dst = *src;
  }
  return dst;
}

int compareInt(const void *lhs, const void *rhs)
{
  const int *ilhs = lhs;
  const int *irhs = rhs;
  if (*ilhs < *irhs)
    return -1;
  else if (*ilhs == *irhs)
    return 0;
  else
    return 1;
}

then you'd call newNode and insert like

void insertIntValue(struct node *root, int value)
{
  struct node *n = newNode(&value, copyInt);
  if (n)
    insert(root, n, compareInt);
}

The big disadvantage of this approach is that you throw type safety right out the window and into oncoming traffic; because we're using void * for everything. the compiler won't be able to catch type mismatches for us. There's nothing to stop you from passing the wrong copy or comparison function to the generic routines for a particular type.

Which brings us to our second disadvantage - you still need to write a type-aware interface (such as the insertIntValue function above) for each data type you want to support (insertFloatValue, insertStringValue, insertMyObnoxiousDataTypeValue, etc.) along with all of the delegates. Partly to avoid type-safety issues, and partly because our "generic" functions really aren't designed to be called directly. For example, the newNode function expects a pointer as the first parameter, meaning you can't write something like

struct node *n = newNode(10, copyInt);

or

struct node *n = newNode(3.14159, copyDouble);

IOW, you can't pass a literal as the first argument; you must pass the address of an object.

The third main disadvantage is you wind up doing a lot of memory management, which is a pain. You have to create copies of your inputs; otherwise, you wind up assigning the same pointer value (the one passed to newNode) to every node in your tree. Every malloc must have a matching free or you will wind up leaking a lot of memory. You have to be disciplined in how you allocate and deallocate your data items.

Building robust generic containers in C is, frankly, a massive pain in the ass. The only real reason to do it is so you can truly appreciate the value of templates in C++ and generics in Java and C#.