N-arios en C

Question

¿Cuál sería una buena implementación de un árbol N-ary en lenguaje C?

Particularmente, quiero implementar un árbol n-ary, no autobalanceado, con un número ilimitado de hijos en cada nodo, en el que cada nodo contiene una estructura ya definida, como esta, por ejemplo:

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

Answer 1

Como primer paso, simplemente puede crear una estructura (llamémosla TreeNode ) que contiene una tarea , así como un conjunto de punteros a TreeNode s. Este conjunto podría ser una matriz (si N es fijo) o una lista vinculada (si N es variable). La lista vinculada requeriría que declare una estructura adicional (llamémosla ListNode ) con un puntero TreeNode al elemento secundario real (parte del árbol) y un puntero al siguiente ListNode en la lista ( nulo si está al final de la lista).

Puede verse más o menos así:

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

Cualquier árbol n-ario puede representarse como un árbol binario donde en cada nodo el puntero izquierdo apunta al primer hijo y el puntero derecho apunta al siguiente hermano.

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

Entonces, su caso sería:

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

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

Esta técnica tiene la ventaja de que muchos algoritmos son más simples de escribir, ya que pueden expresarse en un árbol binario en lugar de en una estructura de datos más complicada.