c - C中的N叉树

Question

哪一个是 C 语言中 N-ary 树的简洁实现？

特别是，我想实现一个 n-ary 树，而不是自平衡树，每个节点中的子节点数量不限，其中每个节点都包含一个已经定义的结构，例如：

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

Answer 1

任何 n 叉树都可以表示为二叉树，其中每个节点的左指针指向第一个孩子，右指针指向下一个兄弟。

             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

作为第一遍，您可以简单地创建一个结构（我们称之为TreeNode），其中包含一个task以及一组指向TreeNode的指针。这个集合可以是一个数组（如果N是固定的）或链表（如果N是可变的）。链表将要求您声明一个附加结构（我们称之为ListNode），其中包含指向实际子节点（树的一部分）的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;
};