尋找完美四叉樹的尺寸

Question

我需要找到一個完美四叉樹的尺寸。 這意味着我有分裂成該分成4個節點等

所以高度1的四叉樹將是尺寸1的節點4 1個根節點 高度2 =尺寸5（1 + 4） 高度3 =尺寸21（1 + 4 + 16） 高度4 = 85的尺寸（1 + 4 + 16 + 64）

等。

我知道一個完美的二進制樹的大小可以與發現： size = 2 ^（height + 1）-1 所以我認爲四叉樹存在類似的方程。

那是什麼？

Answer 1

這是一個geometric series。因此相關公式爲：

S = a * (1 - r^n)/(1 - r) 

其中a是第一值，r是公比，n是項數，和^表示「到最冪」。

Answer 2

對於一個四叉樹的算法是

((4^depth)-1)/3 

例如與深度3你

(64-1)/3 = 21 

，如果你算上三層你

1 + 4 + 16 = 21 

我在執行我甚至將它分成兩個數組 其中所有節點的大小不是l屋檐節點是

((4^(depth-1))-1)/3 

離開節點是

4^(depth-1) 

我做這些計算在編譯時使用的元編程戰俘，以及深度模板參數。所以我只分配兩個數組中的節點。

Answer 3

萬一有人需要一個代碼示例（在swift3）

public func tileCount(forLevelRange levelRange: Range<UInt>) -> UInt64 { 

    var tileCount: UInt64 = 0 
    for level in levelRange.lowerBound ..< levelRange.upperBound { 
     tileCount += UInt64(pow(Double(1 << level), 2)) 
    } 

    return tileCount 
}