竞赛树

Question

我需要构建一个锦标赛树，但是我很困惑如何初始化这个树。我有一组队名。我不明白的是如何初始化数组。例如，如果我有6个团队(a，b，c，d，e，f)，那么我如何构建树，最终得到以下三个。

​

​

我知道这三个节点都有内部和外部节点。我们有n个内部节点和n个外部节点.内部节点存储每场比赛的胜利者，外部存储所有队。这棵树需要平衡。好的，直到现在还清楚，但是，我是如何实现这一点的呢？所有内部节点都需要一个匹配，而外部节点需要一个团队？我怎样才能在比赛中取得平衡呢？

我试图构建一个堆栈，但是它错了，因为e和f匹配，下一个d匹配e和f的胜利者，下一个是c，他与of (d匹配(e匹配f) )匹配。

正如你所看到的，我对此有点困惑，我认为这是我看待问题的方式。我有托盘在网上寻找例子或一些代码来理解，但我找不到任何东西，只是一些讲座如何排序这一数据结构，但没有关于初始化三者。

谢谢

Answer 1

一个想法：

假设有和数组[a,b,c]，您应该使用前两个元素并进行匹配，从数组中删除它们，并将匹配添加到数组的末尾。您一直这样做，直到数组只包含一个元素。

[a, b, c]

[c, match(a, b)]

[match(c, match(a,b))]

Answer 2

总是在一对元素中考虑数组。首先，找到所需的树高：logn(base2) ->舍入到下一个整数，表示高度为m。叶元素数：2^m。

填充从左开始到数组长度的叶节点，其余节点填充空。

在你的例子中：

log6 = 2.something -> 3

2^3 -> 8

在前6位填写a,b,c,d,e,f，让第7位和第8位为空。

希望能帮上忙。