para - Árboles N-ary en C

dime este acertijo

Question

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

Particularmente, quiero implementar un árbol n-ario, sin auto-balanceo, con un número de hijos sin unir en cada nodo, en el que cada nodo tiene una estructura ya definida, como por ejemplo:

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

Answer 1

Cualquier árbol n-ario se puede representar como un árbol binario, donde en cada nodo el puntero izquierdo apunta al primer niño y el puntero derecho apunta al siguiente hermano.

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

Entonces, tu 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 se pueden expresar en un árbol binario en lugar de en una estructura de datos más complicada.

Answer 2

Como primer paso, puede simplemente crear una estructura (llamémoslo TreeNode ) que contiene una tarea , así como un conjunto de punteros a TreeNode . 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émosle 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 del lista).

Puede parecerse a esto:

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