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

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

Particulary, я хочу реализовать n-арное дерево, а не self-ballancing, с несвязанным числом детей в каждом узле, в котором каждый узел содержит уже определенную структуру, например, такую ​​как:

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

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

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

              RR
            / |  \ |
           BCDB - C - D
          / \ |  |  |
         EFGE - FG

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

 struct task { char command[MAX_LENGTH]; int required_time; }; struct node { struct task taskinfo; struct node *firstchild; struct node *nextsibling; }; 

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