C 中的 N 元树

Question

在C语言中，N元树的简洁实现是什么？

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

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

Answer 1

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

这种技术的优点是许多算法更容易编写，因为它们可以在二叉树上表达，而不是在更复杂的数据结构上表达。

Answer 2

作为第一遍，你可以简单地创建一个结构(我们称之为TreeNode(，它包含一个任务，以及一组指向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;
};