为什么将 k-ary 树表示为 left-child、right-sibling 树？
Why represent a k-ary tree as a left-child, right-sibling tree?
我正在阅读流行的算法介绍书 (CLRS)，它介绍了使用 left child, right sibling method 创建 k-ary 树，但我没有看到使用这种方法的好处。它声明我们可以在 k 无界时使用此方法（我们不知道任何 parents 可能提前拥有的 children 的数量）。它还指出，即使 children k 的数量受一个大常数的限制，但大多数节点只有很少的 children，我们也可能会浪费大量内存 space.
对我来说这似乎不是真的。在 C/C++/Java 中，您创建一个结构或 class 类型的 Node 来表示节点的结构。在该结构或 class 中，您创建一个类型数组（C/C++ 的指针）节点，然后通过为 children 中的更多指针重新分配更多内存，您可以表示无限数量的 children =20=]++ 或创建一个包含更多 space 的新数组，并在需要时将指针（引用）移动到 Java 中。
如果我们唯一的选择是在我们的 struct/class 节点表示中创建单个 pointers/references 类型的节点，那么我可以看到如何创建一个 k-ary 其中 k是无界的，或者 k 受一个大常数的限制，我们最终会浪费 space。但是，我们有可以为此目的动态调整大小的数组。我错了吗？这有什么意义？
你既对又错。原则上，我认为这本书指的是与为 children 保留 fixed-size 数组的区别。
我们确实有能够增长的动态数组，但他们通常会分配一个 default-size 数组开始（后来通常在需要更多 space 时将其加倍），所以会有仍然会浪费一小部分内存。
如果您使用单链表，基本上与 left-child 右兄弟方法相同。
当然，其中 none 个是 "wrong"，它们只是在更新、插入、删除等方面具有不同的行为。与任何数据结构一样。
我正在阅读流行的算法介绍书 (CLRS)，它介绍了使用 left child, right sibling method 创建 k-ary 树，但我没有看到使用这种方法的好处。它声明我们可以在 k 无界时使用此方法（我们不知道任何 parents 可能提前拥有的 children 的数量）。它还指出，即使 children k 的数量受一个大常数的限制，但大多数节点只有很少的 children，我们也可能会浪费大量内存 space.
对我来说这似乎不是真的。在 C/C++/Java 中，您创建一个结构或 class 类型的 Node 来表示节点的结构。在该结构或 class 中，您创建一个类型数组（C/C++ 的指针）节点，然后通过为 children 中的更多指针重新分配更多内存，您可以表示无限数量的 children =20=]++ 或创建一个包含更多 space 的新数组，并在需要时将指针（引用）移动到 Java 中。
如果我们唯一的选择是在我们的 struct/class 节点表示中创建单个 pointers/references 类型的节点，那么我可以看到如何创建一个 k-ary 其中 k是无界的，或者 k 受一个大常数的限制，我们最终会浪费 space。但是，我们有可以为此目的动态调整大小的数组。我错了吗？这有什么意义？
你既对又错。原则上，我认为这本书指的是与为 children 保留 fixed-size 数组的区别。
我们确实有能够增长的动态数组，但他们通常会分配一个 default-size 数组开始（后来通常在需要更多 space 时将其加倍），所以会有仍然会浪费一小部分内存。
如果您使用单链表，基本上与 left-child 右兄弟方法相同。
当然，其中 none 个是 "wrong"，它们只是在更新、插入、删除等方面具有不同的行为。与任何数据结构一样。