N-äre Bäume in C

Was wäre eine ordentliche Implementierung eines N-ary-Baums in C-Sprache?

Insbesondere möchte ich einen n-ären Baum implementieren, der sich nicht selbst ausbalanciert, mit einer ungebundenen Anzahl von Kindern in jedem Knoten, in dem jeder Knoten eine bereits definierte Struktur enthält, wie zum Beispiel:

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

Jeder n-äre Baum kann als binärer Baum dargestellt werden, wobei in jedem Knoten der linke Zeiger auf das erste Kind und der rechte Zeiger auf den nächsten Bruder zeigt.

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

Dein Fall wäre also:

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

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

Diese Technik hat den Vorteil, dass viele Algorithmen einfacher zu schreiben sind, da sie auf einem binären Baum statt auf einer komplizierteren Datenstruktur ausgedrückt werden können.

Als ersten Durchgang könnten Sie einfach eine erstellen Struktur (nennen wir es TreeNode) mit a Aufgabesowie eine Reihe von Zeigern auf TreeNodes. Dieser Satz könnte entweder ein Array sein (if N fest ist) oder eine verkettete Liste (falls N ist variabel). Die verknüpfte Liste würde erfordern, dass Sie eine zusätzliche deklarieren Struktur (nennen wir es Listenknoten) mit einer TreeNode Zeiger auf das eigentliche Kind (Teil des Baums) und einen Zeiger auf den nächsten Listenknoten In der Liste (Null wenn am Ende der Liste).

Es könnte etwa so aussehen:

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