（我假设“ 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的位置。我们的算法以以下方式工作：
- 查找包含该节点的图层。
- 虽然不在相关节点上：
- 如果节点在其所在层的上半部分，请向左移动并丢弃范围的右半部分。
- 如果该节点位于其所在层的后半部分，请向右移动并丢弃范围的左半部分。
让我们考虑一下二进制的含义。查找包含该节点的图层 等同于查找数字中设置的最高有效位
。在具有二进制表示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) { int bitIndex = 0; while (true) { if (1 << (bitIndex + 1) > n) break; bitIndex++; } bitIndex--; 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）时间 。
希望这可以帮助！
