N-ary trees in C

Question

Which would be a neat implemenation of a N-ary tree in C language?

Particulary, I want to implement an n-ary tree, not self-ballancing, with an unbound number of children in each node, in which each node holds an already defined struct, like this for example:

struct task {
  char command[MAX_LENGTH];
  int required_time;
};

Answer 1

As a first pass, you could simply create a struct (let's call it TreeNode) which holds a task, as well as a set of pointers to TreeNodes. This set could either be an array (if N is fixed) or a linked list (if N is variable). The linked list would require you to declare an additional struct (let's called it ListNode) with a TreeNode pointer to the actual child (part of the tree), and a pointer to the next ListNode in the list (null if at the end of the list).

It might look something like this:

struct task {
  char command[MAX_LENGTH];
  int required_time;
};

struct TreeNode;

struct ListNode {
  struct TreeNode * child;
  struct ListNode * next;
};

struct TreeNode {
  struct task myTask;
  struct ListNode myChildList;
};

Answer 2

Any n-ary tree can be represented as a binary tree where in each node the left pointer points to the first child and the right pointer points to the next brother.

             R                        R
           / | \                      |
          B  C  D                     B -- C -- D
         / \    |                     |         |
        E   F   G                     E -- F    G

So, your case would be:

struct task {
  char command[MAX_LENGTH];
  int required_time;
};

struct node {
  struct task taskinfo;
  struct node *firstchild;
  struct node *nextsibling;
};

This technique has the advantage that many algorithms are simpler to write as they can be expressed on a binary tree rather than on a more complicated data structure.