根据this article，
树的根在位置L(k)-1。
Ltk-1子树的根在位置L(k-1)-1。
Ltk-2子树的根在位置L(k)-2。
有人可以帮我理解吗？我正在尝试实现Smoothsort。
最佳答案
假设您在数组中存储了一个k阶的Leonardo堆，然后递归进行布局，以便始终布置较大的子树，然后依次布置较小的子树和根节点。这意味着数组中将总共有L(k)个节点，其位置编号为0、1、2、3 ...，L(k)-1。它将看起来像这样:
+---------------------------+----------------------+------+
| Tree of order k - 1 | Tree of order k - 2 | root |
+---------------------------+----------------------+------+
注意，根在最后，所以它在位置L(k)-1上，因为我们使用零索引。
那么这两个子树在哪里？好吧，k-2阶子树紧接在根节点之前。它的布局方式是其根在最右边。因此，要找到它的根，我们转到整棵树的根(位置L(k)-1)，然后备份一步，直到位置L(k)-2。
那么k-1阶子树呢？好吧，请注意，它很舒适地位于我们代表的最前面。它的根节点将在该块的末尾，即位置L(k-1)-1(类似于我们更大的k阶树的根在位置L(k)-1的情况。)
希望您喜欢我的文章! :-)