寻找完美四叉树的大小

Question

我需要找到一个完美四叉树的大小。这意味着我有一个根节点，它分裂成4个节点，然后每个节点再分裂成4个节点，依此类推。

因此，高度为1的四叉树大小为1； 高度为2的四叉树大小为5（1 + 4）； 高度为3的四叉树大小为21（1 + 4 + 16）； 高度为4的四叉树大小为85（1 + 4 + 16 + 64）；

等等。

我知道完美二叉树的大小可以通过以下公式找到：size = 2^(height+1)-1

所以我相信存在一个类似的公式适用于四叉树。

那么这个公式是什么？

- Pubby

Answer 1

这是一个等比数列。因此相关的公式为：

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

其中a表示第一个值，r表示公比，n表示项数，^表示乘方。

- Oliver Charlesworth

Answer 2

四叉树的算法如下：

((4^depth)-1)/3

例如，深度为3时，您将获得以下结果。

(64-1)/3 = 21

如果您计算三层，您将得到

1 + 4 + 16 = 21

在我的实现中，我甚至将它分成了两个数组，其中所有非叶子节点的大小为。

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

并且离开节点是：

4^(depth-1)

我使用元编程在编译时进行幂运算的计算，并使用模板参数来确定深度。因此，我只需在两个数组中分配我的节点。

- Bozemoto

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
}

- ambientlight