N-арные деревья в Си

Question

Что было бы аккуратной реализацией N-арного дерева на языке Си?

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

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

Answer 1

В качестве первого шага вы можете просто создать структуру (назовем ее TreeNode), которая содержит задачу, а также набор указателей на TreeNode. Этот набор может быть либо массивом (если 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;
};

Answer 2

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

             RR
           / | \ |
          BCDB - C - D
         / \    |                     |         |
        E   F   G                     E - FG

Итак, ваш случай будет:

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

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

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