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;
};

By N-ary, you mean a tree with fanout-degree N? You have to specify more, for example not-self-balancing search tree, trie, B-tree, etc. — ephemient, Oct 10 '08 at 01:59
You are right, I'll edit the question to add some more detail. Thanks! And thanks Matt J too for your answer! — mmutilva, Oct 10 '08 at 03:05

Remo.D · Answer 1 · 2008-10-10T16:29:00.827

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.

score 14 · Accepted Answer · answered Oct 10 '08 at 02:21

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;
};

N-ary trees in C

2 Answers2

Linked