关于如何在二叉树算法的第j层中检索第i个元素的讨论

Question

我正在解决一个名为codefights的网站上的一些问题，最后一个解决的是关于二叉树的问题，其中：

考虑一个特殊的工程师和医生家庭。这个家庭有以下规则：

每个人都有两个孩子。工程师的第一个孩子是工程师，第二个孩子是博士。医生的第一个孩子是医生，第二个孩子是工程师。一代又一代的博士和工程师都是从工程师开始的。

我们可以用这张图来表示这种情况：

            E
       /         \
      E           D
    /   \        /  \
   E     D      D    E
  / \   / \    / \   / \
 E   D D   E  D   E E   D

给定一个人在上面祖先树中的等级和位置，找到这个人的职业。注意：在这棵树中，第一个孩子被视为左孩子，第二个孩子被视为右孩子。

由于有一些空间和时间限制，解决方案不能基于实际构建树，直到所需的级别并检查哪个元素在所要求的位置。到现在为止还挺好。我用python编写的建议解决方案是：

def findProfession(level, pos):

    size = 2**(level-1)
    shift = False    

    while size > 2:
        if pos <= size/2:
            size /= 2
        else:
            size /= 2
            pos -= size
            shift = not shift

    if pos == 1 and shift == False:
        return 'Engineer'
    if pos == 1 and shift == True:
        return 'Doctor'
    if pos == 2 and shift == False:
        return 'Doctor'
    if pos == 2 and shift == True:
        return 'Engineer'

当它解决了这个问题时，我访问了其他使用过的解决方案，我对这个感到惊讶：

def findProfession(level, pos):
    return ['Engineer', 'Doctor'][bin(pos-1).count("1")%2]

更重要的是，我不明白它背后的逻辑，所以我们来到了这个问题。有人可以向我解释这个算法吗？

Answer 1

让我们按以下方式对树的节点进行编号：

1) 根的编号为 1

2) 节点 x 的第一个子节点的编号为 2*x

3) 节点 x 的第二个孩子的编号为 2*x+1

现在，请注意，每次转到第一个子节点时，职业保持不变，并且在节点的二进制表示中添加 0。每次你去找第二个孩子时，职业都会翻转，你在二进制表示中加一个 1。

示例： 让我们在第 4 级（问题中的图表中的最后一个级别）中找到第 4 个节点的职业。首先，我们从编号为 1 的根开始，然后转到编号为 2（二进制 10）的第一个子节点。之后，我们转到 2 的第二个孩子，即 5（101 二进制）。最后，我们转到 5 的第二个孩子，即 11（1011 二进制）。

请注意，我们开始时只有一位等于 1，然后我们向二进制表示中添加的每 1 位都会翻转专业。所以我们翻转一个职业的次数等于（位数等于1）-1。这个数量的奇偶性决定了这个职业。

这使我们得出以下解决方案：

X = [ 2^(level-1) + pos - 1 ] 中等于 1 的位数

Y = (X-1) 模 2

如果 Y 是 0 那么答案是“工程师”否则答案是“医生”

由于 2^(level-1) 是 2 的幂，它正好有一位等于 1，因此您可以这样写：

X = [ pos-1 ] 中等于 1 的位数

Y = X 模 2

这等于您在问题中提到的解决方案。