我正在阅读流行的算法介绍书 (CLRS)，它使用 left child, right sibling method 创建 k 元树。但我没有看到使用这种方法的好处。它声明我们可以在 k 无界时使用此方法(我们不知道任何 parent 可能提前拥有的 child 的数量)。它还指出，即使 child 的数量 k 受一个大常数的限制，但大多数节点只有很少的 child ，我们也可能会浪费大量的内存空间。
对我来说这似乎不是真的。在 C/C++/Java 中，您创建一个类型为 Node 的结构或类来表示节点的结构。在该结构或类中，您创建一个类型的数组(C/C++ 的指针)节点，然后通过为 C/C++ 中的更多指针重新分配更多内存或创建具有更多空间和移动的新数组，您可以代表无限数量的 child 需要时 Java 中的指针(引用)。
如果我们唯一的选择是在我们的节点的结构/类表示中创建单独的节点类型的指针/引用，那么我可以看到创建一个 k 元是不可能的，其中 k 是无界的或 k 是有界的一个很大的常数，我们最终会浪费空间。但是，我们有可以为此目的动态调整大小的数组。我错了吗？这有什么意义？
最佳答案
你既对又错。原则上，我认为这本书指的是与为 children 保留固定大小的数组的区别。
我们确实有能够增长的动态数组，但它们通常会在开始时分配一个默认大小的数组(后来通常在需要更多空间时将其加倍)，因此仍然会有一小部分内存被浪费.
如果您要使用，比如说，一个单链表，您基本上会做与左子右兄弟方法相同的事情。
当然，这些都不是“错误”的，它们只是对更新、插入、删除等有不同的行为。与任何数据结构一样。
关于java - 为什么将 k-ary 树表示为左子树、右兄弟树？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29138200/