Arbres N-ary en C

Qui serait un pur la mise en oeuvre d'un N-aire arbre en langage C?

Particulièrement, je tiens à mettre en œuvre un n-aire d'arbre, pas d'auto-ballancing, avec un indépendant nombre d'enfants dans chaque nœud, dans lequel chaque nœud est titulaire d'un déjà défini struct, comme ceci par exemple:

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

source d'informationauteur mmutilva

  1. 12

    Comme une première passe, vous pouvez simplement créer un struct (appelons TreeNode) qui est titulaire d'un tâcheainsi que d'un ensemble de pointeurs vers TreeNodes. Cet ensemble pourrait être soit un tableau (si N est fixe) ou une liste chaînée (si N est variable). La liste serait vous obliger à déclarer supplémentaires struct (appelé ListNode) avec un TreeNode pointeur vers le réel de l'enfant (la partie de l'arbre), et un pointeur vers la prochaine ListNode dans la liste (null si à la fin de la liste).

    Il pourrait ressembler à quelque chose comme ceci:

    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;
};
  2. 50

    N-ary arbre peut être représenté comme un arbre binaire où chaque nœud de la gauche d'un pointeur vers le premier enfant et le droit d'un pointeur sur la prochaine frère.

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

    Donc, votre cas serait:

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

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

    Cette technique a l'avantage que de nombreux algorithmes sont plus simples à écrire, car ils peuvent être exprimées sur un arbre binaire plutôt que sur les plus compliquées de la structure de données.