錦標賽樹

Question

我需要建立錦標賽樹，但我很困惑如何初始化樹。我有一組隊名。我不明白的是如何初始化數組。例如，如果我有6支隊伍（a，b，c，d，e，f），我如何構建這棵樹才能結束後面的三個。

我知道，這三者有內部和外部的節點。我們有n - 1內部節點，和n外部節點。內部節點存儲每場比賽的勝者，外部存儲所有隊伍。樹需要平衡。好吧，直到現在它清楚，但是，我如何執行此？所有內部節點需要匹配，外部節點需要成爲一個團隊？而我如何才能爲比賽創造一個平衡點？

我嘗試建立一個堆棧，但它錯了，因爲e和f比賽，下一個d配以e和f的贏家，但下一個就是c和他比賽（d匹配（e匹配f））。

正如你所看到的，我對此有點困惑，我認爲是我看待問題的方式。我有托盤在互聯網上查看例子或理解代碼，但我找不到任何東西，只是一些講座如何訂購這個數據結構，但沒有關於初始化這三個。

感謝

Answer 1

一個想法：

比方說，喲必須和數組[a,b,c]，你應該採取的第一個2個元素進行匹配，從陣列中刪除，並在比賽添加到年底陣列。你一直這樣做直到數組只包含一個元素。

[a, b, c]

[c, match(a, b)]

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

Answer 2

始終考慮在一對元件的陣列。 首先，找到所需樹的高度：logn(base2) - >舍入爲下一個整數，比如高度爲m。 葉片元件數量：2^m。

填充從左到左的葉子節點，併爲其餘節點填充null。

在您的例子：

log6 = 2.something -> 3 

2^3 -> 8 

填寫第6位a,b,c,d,e,f，讓第7和第8位爲空。

希望它有幫助。