c++ - 寻找完美四叉树的大小

Question

我需要找到完美四叉树的大小。 这意味着我有 1 个根节点 split 成 4 个节点， split 成 4 个节点等。

所以高度为 1 的四叉树的大小为 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是项数，^ 表示“to-the-power-of”。