（我假设“ kth元素（按BFS顺序）”是从输入的从上到下，从左到右扫描的角度表示第k个元素。）

由于您知道二叉堆是完整的二叉树（可能在最后一级除外），因此您知道树的形状是具有一定高度（包含2
k个节点，k个节点）的完美二叉树。节点从左到右填充。当您写出图片中的节点编号并将值一索引时，就会出现这些树的一个真正漂亮的属性：

                      1
            2                3
        4       5        6       7
       8 9    10 11    12 13   14 15

请注意，每个层都以一个2的幂的节点开始。因此，假设我们想查找数字13。两个不小于13的最大幂是8，因此我们知道13必须出现在行中

  8  9 10 11 12 13 14 15

现在，我们可以使用此知识对从13到树的根的路径进行反向工程。例如，我们知道该行数字的后半部分中有13个，这意味着13个属于根的右子树（如果它属于左子树，那么我们将位于包含8、9、10和11。）这意味着我们可以从根开始，直接舍弃一半的数字以获得

12 13 14 15

我们现在在树中的节点3处。那么我们是左走还是右走？好吧，在这些数字的前半部分中有13，因此我们知道此时需要下降到节点3的左子树中。这将我们带到节点6，现在我们剩下了前半部分。数字：

12 13

13在这些节点的右半部分，所以我们应该下降到右侧，将我们带到节点13。瞧！在那里！

那么这个过程是如何进行的呢？好吧，我们可以使用一个非常非常可爱的技巧。让我们用二进制写出上面相同的树：

                        0001
            0010                    0011
      0100        0101        0110        0111
   1000  1001  1010  1011  1100  1101  1110  1111
                                 ^^^^

我已经指出了节点13的位置。我们的算法以以下方式工作：

1. 查找包含该节点的图层。
2. 虽然不在相关节点上：
   1. 如果节点在其所在层的上半部分，请向左移动并丢弃范围的右半部分。
   2. 如果该节点位于其所在层的后半部分，请向右移动并丢弃范围的左半部分。

让我们考虑一下二进制的含义。查找包含该节点的图层 等同于查找数字中设置的最高有效位
。在具有二进制表示1101的13中，MSB是8位。这意味着我们处于以8开始的层中。

那么，如何确定我们是在左侧子树中还是右侧子树中？好吧，要做到这一点，我们需要查看我们是在本层的上半部还是在下半部。现在，让我来 看看
一个可爱的花招- 看看MSB之后的下一部分
。如果此位设置为0，则我们在范围的前一半，否则，我们在范围的后一半。因此，我们可以通过查看数字的下一位来确定范围的一半！这意味着我们可以通过仅查看数字的下一位来确定要落入哪个子树。

完成此操作后，我们可以重复此过程。在下一级别我们将做什么？好吧，如果下一位为零，我们往左走；如果下一位为一，我们往右走。看看这对13意味着什么：

 1101
  ^^^
  |||
  ||+--- Go right at the third node.
  ||
  |+---- Go left at the second node.
  |
  +----- Go right at the first node.

换句话说，我们只需查看MSB之后的数字位，就可以阐明从树的根到所讨论节点的路径！

这是否总是有效！你打赌！让我们尝试数字7。它的二进制表示形式为0111。MSB位于4的位置。使用我们的算法，我们可以这样做：

0111
  ^^
  ||
  |+--- Go right at the second node.
  |
  +---- Go right at the first node.

从原始图片看，这是正确的选择！

这是此算法的一些粗略的C / C ++伪代码：

Node* NthNode(Node* root, int n) {
    /* Find the largest power of two no greater than n. */
    int bitIndex = 0;
    while (true) {
        /* See if the next power of two is greater than n. */
        if (1 << (bitIndex + 1) > n) break;
        bitIndex++;
    }

    /* Back off the bit index by one.  We're going to use this to find the
     * path down.
     */
    bitIndex--;

    /* Read off the directions to take from the bits of n. */
    for (; bitIndex >= 0; bitIndex--) {
        int mask = (1 << bitIndex);
        if (n & mask)
            root = root->right;
        else
            root = root->left;
    }
    return root;
}

我尚未测试此代码！ 用唐·努斯（Don Knuth）的话来说，我刚刚证明了它在做正确的事情。我可能在这里有一个错误的错误。

那么这段代码有多快？好吧，第一个循环运行，直到找到大于n的2的第一个幂，这需要O（log
n）时间。循环的下一部分一次通过n个位向后计数，在每一步执行O（1）工作。因此，整个算法总共花费 O（log n）时间 。

希望这可以帮助！