N-арные деревья в C

Что было бы аккуратным воплощением N-арного дерева на языке C?

Частично, я хочу реализовать n-арное дерево, а не самобалластирование, с несвязанным числом детей в каждом node, в котором каждый node содержит уже определенную структуру, например, это:

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

Ответ 1

В качестве первого прохода вы можете просто создать структуру (пусть вызовет ее TreeNode), которая содержит задание, а также набор указателей на TreeNodes. Этот набор может быть либо массивом (если фиксировано N), либо связанным списком (если N). Связанный список потребует, чтобы вы объявили дополнительную структуру (пусть называли ее ListNode) указателем TreeNode к фактическому дочернему элементу (части дерева) и указателю на следующий ListNode в списке ( null если в конце списка).

Он может выглядеть примерно так:

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

Ответ 2

Любое n-арное дерево может быть представлено как двоичное дерево, где в каждом node левый указатель указывает на первого ребенка, а правый указатель указывает на следующего брата.

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

Итак, ваше дело будет:

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

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

Этот метод имеет то преимущество, что многие алгоритмы проще писать, поскольку они могут быть выражены на двоичном дереве, а не на более сложной структуре данных.