二叉树算法j级中如何检索第一元素的讨论

Question

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

考虑一个由工程师和医生组成的特殊家庭。这个家庭有以下规则： 每个人都有两个孩子。工程师的第一个孩子是工程师，第二个孩子是医生。医生的第一个孩子是医生，第二个孩子是工程师。一代又一代的医生和工程师都是从工程师开始的。 我们可以使用这个图表来表示情况： E/D、D/D、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=比特数等于1/2^(级别-1)+pos-1

Y= (X-1) mod 2

如果Y是0，那么答案是"Engineer“，否则答案是”医生“

由于2 ^(级别-1)是2的幂，它的位数正好等于1，因此您可以写：

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

Y=2

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

Answer 2

这种类型的序列称为Thue-Morse序列。使用同一棵树，这里演示了为什么它给出了正确的答案：

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]