c - 如何用 C 语言实现数组构建 k 叉树？

Question

我正在做一个关于 C 语言 k 叉树的大学项目。该练习需要构建一个 k 叉树作为列表并将其移植到一个数组中。目前我可以成功地将 k 叉树构建为列表，现在我正在尝试构建带有数组实现的 k 叉树。

请注意，我的 k 叉树的结构由一个子节点和“k”个兄弟节点组成。例如:

4 (root)
.
.
5---6---23---98
    .
    .
    78---53---22---19

所以，关于 k 叉树的数组实现，我想使用类似的东西:

typedef struct {
      int value;
      int children[MAX];
} Karyarray;

Karyarray array[MAX];

...但我不知道如何最终存储以前的 child 作为 parent 的 child (和 sibling )。我希望我已经说清楚了。那么，你有一个用数组实现 k 叉树的最佳方法吗？能给我举个例子吗？

Answer 1

为什么不像通常使用二叉树那样做，在节点结构中放置一个指向其每个子节点的指针，唯一的区别是现在你有 k 个子节点而不是两个，所以最简单的方法可以将所有子指针存储在指针数组中:

 struct treeNode {
   int              value;
   struct treenode *children[K];
 };

因此，要进入第 i 个 child ，您需要执行以下操作:

 child = parent->children[i];