algorithm - 在第 N 层二叉树中找到第 k 个节点

Question

可能重复：
堆树中的第 K 个元素

给定一棵二叉树，如果 parent 为 0，则左孩子为 0，右孩子为 1。如果 parent 为 1，则左孩子为 1，右孩子为 0。树的根为 0。找到第 k 个节点值存在于第 N 级

我试图以这种方式解决。假设第一级有0，第二级有01，第三级有 01 - 10（即前半部分的补码）。
同样0110 1001在第四层。

现在我如何概括这个解决方案或任何其他方式来解决这个问题？

score 3 · Accepted Answer

^{为了概括您的想法，您可以编写一个递归过程，给出树的第n}级元素的列表，因为（如您所说）每个级别都可以通过连接上层及其补码获得：

getLevel(level)

  if level == 0
    return [0]

  upperLevel = getLevel(level - 1)

  return upperLevel + complement(upperLevel)

列表在哪里[...]，是列表和更改的+串联，反之亦然。complement01

有了这个，您只需要获取由生成的列表的k^{第 th}元素getLevel(n)。

这可能不是最佳解决方案，它只是建立在您的想法之上（而且很容易）。

score 2 · Accepted Answer

我手动生成了前几位，得到了 0110100110010110。谷歌显示这是Thue-Morse 序列。OEIS 中的序列A010060。OEIS 页面上的评论有这一行：

a(n) = S2(n) mod 2，其中 S2(n) = n 的数字之和，n 以 2 为底表示法。

这n是您的情况k，而N您的情况无关紧要。因此，要确定 a(n) 计算 1 的数量n，并取该总和的最低有效位。

2 回答 2