CODEWITHSUNDEEP
ctreenodes
xena12
xena12

Reputation: 17

How can I create tree in C that has different types of values in nodes?

I have to make a tree that has one types of values in all nodes except leaves and I'm not sure how to do that or is it even possible. E.g. int in all nodes but char in leaves. I'm new at programming so I would really appreciate your help. Thanks

Upvotes: 0

Views: 1184

Answers (3)

AlbusMPiroglu
AlbusMPiroglu

Reputation: 653

I partially agree with Lundin and Paul. I would keep the data as void*, and check a node to see if it's a leaf by checking the right & left to be NULL or not. Here is something simple to begin with:

#include <string.h>

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

int isLeaf(node* n)
{
    return n->right == NULL && n->left == NULL;
}

/* you can also make the two functions below a macro, but that's off-topic */
void addInt(node* n, int i)
{
    n->data = malloc(sizeof(int));
    memcpy(n->data, &i, sizeof(int));
}

void addChar(node* n, char i)
{
    n->data = malloc(sizeof(char));
    memcpy(n->data, &i, sizeof(char));
}

node* node_new()
{
    node* root = malloc(sizeof(node));
    root->right = NULL;
    root->right = NULL;
}

int main()
{
    node* root = node_new();
    addInt(root, 3);

    /* assume you have some node* n1 */
    if (n1->isLeaf())
      addChar(n1, 't');
}

Upvotes: 0

Lundin
Lundin

Reputation: 213458

The canonical way to store a generic type would be this:

typedef enum
{
  TYPE_INT,
  TYPE_STR,
} type_info_t;

typedef struct node_t
{
  struct node_t* left;
  struct node_t* right;
  void*          data;  
  type_info_t    type;
} node_t;


...

int some_value = 1;
node_t node1 = {NULL, NULL, &some_value, TYPE_INT};
node_t node2 = {NULL, NULL, "hello",     TYPE_STR};

You should avoid creating "variants" by using unions, doing so is bad practice:

  • Variants don't scale well at all during maintenance. If you need to add a larger type than those present, the data will grow accordingly. A variant can never be smaller than its largest member + padding bytes.

  • They are inefficient, allocating more memory than needed, including padding for the worst case.

  • The different types in a variant do not necessarily have the same alignment requirements, if they are of different sizes. The alignment within in variant is unspecified. Similarly, endianess could be an issue.

  • Code using variants can be hard to read and understand. One can make mistakes such as first writing a small type, then reading a larger type, with the result that the larger type partially contains indeterminate data.

  • You can only initialize one member in the variant explicitly. This means that if the variant was initialized by setting member x, and is then used by accessing member y, then member y could contain an indeterminate value.

(The above covers most of the rationale from MISRA-C:2012 rule 19.2)

Upvotes: -1

Paul Ogilvie
Paul Ogilvie

Reputation: 25266

As in your case it is known what the nodes store (ints in nodes and chars in leaves), it is sufficient to check if a node is a leaf, i.e. if left and right are null. Then use a union for value:

struct MYTREE {
    struct MYTREE *left, *right;
    union {
        char *charval;
        int intval;
    } value;
};

Upvotes: 3

Related Questions