c++ - 如何确定树中的元素（锦标赛括号）？

Question

假设我们有以下树：

1
    9
2
        13
3
    10
4 
            15
5
    11
6 
        14
7   
    12
8

其中元素（匹配）：
1-8 是第 1 轮
9-12 是第 2 轮
13-14 是第 3 轮
15 是第 4 轮

如何确定树中元素“n”的轮次？

我目前的公式是：

total_rounds = floor(log(totalTeams,2));

matches_per_round = (totalTeams / pow(2, current_round))

next_match_id = (totalTeams/2) + ceil(match_id/2)

total_matches = total_teams - 1

Answer 1

想象一下这棵树的编号是相反的。

15
     7
14
         3
13 
     6
12 
             1
11
     5 
10 
         2
9   
     4
8

在这种情况下，它只是数字的对数，四舍五入。现在我们只需从轮数中减去这个数字，我们就完成了。

reverse_number = total_matches - match_number + 1;
reverse_match_round = floor(log(reverse_number, 2));
match_round = total_rounds - match_round;

（注意，reverse_match_round实际上是 0 索引，与 match_round 不同。但是，由于我们从 中减去它total_rounds，因此保持这种方式比 1 索引更容易。如果您更喜欢 1 索引，只需添加+1到最后两个中的每一个行。）