Arbres N-aires en C

Question

Quelle serait la bonne implémentation d’un arbre N-aire en langage C?

En particulier, je souhaite implémenter un arbre n-aire, non auto-équilibrant, avec un nombre non lié d'enfants dans chaque nœud, dans lequel chaque nœud contient une structure déjà définie, comme par exemple:

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

Answer 1

Dans un premier temps, vous pouvez simplement créer une structure (appelons-la TreeNode ) qui contient une tâche , ainsi qu'un ensemble de pointeurs sur TreeNode . Cet ensemble peut être un tableau (si N est fixe) ou une liste chaînée (si N est variable). La liste chaînée vous obligerait à déclarer une structure supplémentaire (appelons-la ListNode ) avec un pointeur TreeNode sur l'enfant réel (partie de la arborescence) et un pointeur sur le prochain ListNode de la liste ( null s'il se trouve à la fin de la liste).

Cela pourrait ressembler à quelque chose comme ceci:

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

Tout arbre n-aire peut être représenté comme un arbre binaire où, dans chaque nœud, le pointeur de gauche pointe vers le premier enfant et le pointeur de droite pointe vers le prochain frère.

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

Votre cas serait donc:

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

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

Cette technique présente l'avantage que de nombreux algorithmes sont plus simples à écrire car ils peuvent être exprimés sur un arbre binaire plutôt que sur une structure de données plus complexe.