CのN分木

Question

C言語のN項ツリーの適切な実装はどれですか？

特に、各ノードにバインドされていない数の子を持つ自己バランシングではなく、n-aryツリーを実装します。各ノードは、たとえば次のように、既に定義された構造を保持します。

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

Answer 1

最初のパスとして、 task を保持する struct （ TreeNode と呼びます）を作成するだけです。 TreeNode へのポインターのセット。このセットは、配列（ N が固定の場合）またはリンクリスト（ N が可変の場合）のいずれかです。リンクリストでは、実際の子（ TreeNode へのポインター）を持つ追加の struct （ ListNode と呼びます）を宣言する必要があります。ツリー）、およびリスト内の次の ListNode へのポインター（リストの最後にある場合は null ）。

次のようになります：

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

任意のn項ツリーは、各ノードで左ポインターが最初の子を指し、右ポインターが次の兄弟を指す二分木として表すことができます。

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

だから、あなたのケースは次のようになります：

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

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

この手法には、より複雑なデータ構造ではなくバイナリツリーで表現できるため、多くのアルゴリズムの記述が簡単であるという利点があります。