N-ary Bäume in C

Question

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

Insbesondere möchte ich einen n-fachen Baum implementieren, der sich nicht selbst ausbalanciert, mit einer unbegrenzten 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;
};

Answer 1

Als ersten Durchgang könnten Sie einfach eine erstellen Struktur (nennen wir es TreeNode), die a enthält Aufgabe, sowie eine Reihe von Zeigern auf TreeNodeS.Diese Menge könnte entweder ein Array sein (wenn N fest ist) oder eine verknüpfte Liste (falls N ist variabel).Für die verknüpfte Liste müssten Sie eine zusätzliche Angabe machen Struktur (nennen wir es ListNode) mit einem TreeNode Zeiger auf das eigentliche untergeordnete Element (Teil des Baums) und ein Zeiger auf das nächste ListNode 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;
};

Answer 2

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

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

Ihr 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 eher auf einem binären Baum als auf einer komplizierteren Datenstruktur ausgedrückt werden können.