algorithm - 二叉树算法第j层中如何取出第i个元素的讨论

Question

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

Consider a special family of Engineers and Doctors. This family has the following rules:

Everybody has two children. The first child of an Engineer is an Engineer and the second child is a Doctor. The first child of a Doctor is a Doctor and the second child is an Engineer. All generations of Doctors and Engineers start with an Engineer.

We can represent the situation using this diagram:

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

Given the level and position of a person in the ancestor tree above, find the profession of the person. Note: in this tree first child is considered as left child, second - as right.

由于有一定的空间和时间限制，解决方案不能基于实际构建树直到所需的级别并检查哪个元素在要求的位置。到目前为止，一切都很好。我提出的用 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的第一个 child 的编号为2*x

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

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

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

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

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

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

Y = (X-1) mod 2

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

因为 2^(level-1) 是 2 的幂，它正好有一位等于 1，因此你可以写:

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

Y = X 模 2

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