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

Question

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

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

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

Answer 1

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

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

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-арное дерево может быть представлено в виде двоичного дерева, где в каждом узле левый указатель указывает на первого потомка, а правый указатель указывает на следующего брата.

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

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