如何检索二叉树算法中第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]

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

- Randerson

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) mod 2

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

由于2^(level-1)是2的幂，因此它只有一个等于1的位，因此可以写为：

X = [ pos-1 ] 的二进制表示中等于1的位数

Y = X mod 2

这与您在问题中提到的解决方案相同。

- DPDP

---

非常好的答案和问题解决方案。我希望你能够加以说明，这样就更容易理解了。我不得不读了几遍。谢谢！ - patito

Answer 2

这种序列被称为Thue-Morse sequence。使用同样的树，下面是一个演示，说明它为什么会给出正确的答案:

p是从0开始计数的位置

b是p的二进制表示

c是b中1的数量

                  p0
                   E
                  b0
                  c0
            /            \
         p0                p1
         E                  D
        b0                 b1
        c0                 c1
    /        \         /        \
   p0        p1       p2        p3
   E          D        D         E
   b0        b1       b10       b11
   c0        c1       c1         c2
  /  \      /  \     /  \       /  \
p0   p1   p2   p3   p4   p5   p6   p7
 E    D    D    E    D    E    E    D
b0   b1   b10  b11  b100 b101 b110 b111
c0   c1   c1   c2    c1   c2   c2   c3

c 对于工程师始终是偶数，对于医生始终是奇数。因此：

index = bin(pos-1).count('1') % 2
return ['Engineer', 'Doctor'][index]

- Julian Hernandez