Alberi di N-ary in C

Question

Quale sarebbe un'implementazione ordinata di un albero N-ary in linguaggio C?

In particolare, voglio implementare un albero n-ary, non auto-bilanciato, con un numero illimitato di figli in ciascun nodo, in cui ogni nodo contiene una struttura già definita, come questo ad esempio:

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

Answer 1

Come primo passaggio, potresti semplicemente creare un struct (chiamiamolo TreeNode ) che contiene un task , oltre a un set di puntatori su TreeNode s. Questo set può essere un array (se N è fisso) o un elenco collegato (se N è variabile). L'elenco collegato richiederebbe di dichiarare un struct aggiuntivo (chiamiamolo ListNode ) con un puntatore TreeNode al figlio effettivo (parte del albero) e un puntatore al ListNode successivo nell'elenco ( null se alla fine dell'elenco).

Potrebbe assomigliare a questo:

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

Qualsiasi albero n-ary può essere rappresentato come un albero binario in cui in ogni nodo il puntatore sinistro punta al primo figlio e il puntatore destro punta al fratello successivo.

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

Quindi, il tuo caso sarebbe:

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

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

Questa tecnica ha il vantaggio che molti algoritmi sono più semplici da scrivere in quanto possono essere espressi su un albero binario piuttosto che su una struttura di dati più complicata.