árboles N-arios en C

Question

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

Particularmente, quiero poner en práctica un árbol n-ario, no auto-ballancing, con un número no unido de los niños en cada nodo, en el que cada nodo tiene una estructura ya definida, así por ejemplo:

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

Answer 1

como primer paso, simplemente podría crear una estructura (llamémoslo NodoArbol) que tiene una tarea , así como un conjunto de punteros a NodoArbol s. Este conjunto podría ser una matriz (si se corrigió N) o una lista vinculada (si N es variable). La lista enlazada que requieren volver a declarar un estructura adicional (vamos lo llamaron NodoLista) con un NodoArbol puntero al niño real (parte del árbol), y un puntero al siguiente NodoLista en la lista (nulo si está al final de la lista).

Podría ser algo como 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; 
}; 

Answer 2

Cualquier árbol n-ario se puede representar como un árbol binario en el que en cada nodo apunta el puntero de izquierda al primer hijo y el puntero apunta recto con respecto a la próxima hermano.

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

Por lo tanto, 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 fáciles de escribir, ya que pueden ser expresadas en un árbol binario en lugar de en una estructura de datos más complicado .