Árvores n-ary em c

Question

Qual seria uma implemenação elegante de uma árvore n-ara em C linguagem?

Particular, eu quero implementar uma árvore n-ara, não auto-balanceamento, com um número não ligado de crianças em cada nó, no qual cada nó mantém uma estrutura já definida, como esta, por exemplo:

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

Answer 1

Como primeiro passe, você pode simplesmente criar um estrutura (Vamos chamá -lo Treenode) que contém um tarefa, bem como um conjunto de ponteiros para Treenodes. Este conjunto pode ser uma matriz (se N é fixo) ou uma lista vinculada (se N é variável). A lista vinculada exigiria que você declarasse um adicional estrutura (Vamos chamá -lo ListNode) com um Treenode ponteiro para a criança real (parte da árvore) e um ponteiro para o próximo ListNode na lista (nulo se no final da lista).

Pode parecer algo assim:

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

Qualquer árvore N-Ear pode ser representada como uma árvore binária, onde em cada nó o ponteiro esquerdo aponta para o primeiro filho e o ponteiro certo aponta para o próximo irmão.

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

Então, seu caso seria:

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

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

Essa técnica tem a vantagem de que muitos algoritmos são mais simples de escrever, pois podem ser expressos em uma árvore binária, e não em uma estrutura de dados mais complicada.