c - C の N 分木

Question

C 言語での N-ary ツリーの適切な実装はどれですか?

特に、自己分散ではなく、各ノードにバインドされていない数の子を使用して、各ノードが既に定義されている構造体を保持する n 分木を実装したいと考えています。たとえば、次のようになります。

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

Answer 1

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

             RR
           / | \ |
          BCDB --C --D
         / \ | | |
        EFGE-FG

したがって、あなたのケースは次のようになります。

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

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

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

Answer 2

最初のパスとして、単純にtaskとTreeNodeへの一連のポインタを保持する構造体( TreeNodeと呼びましょう) を作成できます。このセットは、配列 ( Nが固定の場合) または連結リスト ( Nが可変の場合) のいずれかです。リンクされたリストでは、実際の子 (ツリーの一部) へのTreeNodeポインターと、リスト内の次の 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;
};