0xb*_*00d 6 graphics tree computer-science rendering computational-geometry
令为四叉树N中的内部节点数。为什么叶子的数量等于？我不明白我们需要如何争论。1 + 3 * N
ven*_*nk8 11
TLDR：叶节点数量=3 * 内部节点数量 + 1
我想以@Sneftel 的答案为基础。
令L 1、L 2、L 3表示当内部节点有1、2、3个时叶节点的数量。
每当我们添加一个内部节点时，就会损失 1 个叶节点，并=从之前的叶节点数值中增加 k 个叶节点（在四边形 k 4 中）。
我们从基本条件 L 1 = k 开始，只是根节点 k 个子节点（=四叉树中的 k 4 ）
例如：
L 2 = L 1 - 1 + k
L 3 = L 2 - 1 + k
一般来说，
L n = L n-1 -1 + k ，其中 n 是内部节点的数量，k 是分支因子（=四叉树中的 k 4 ）
让我们扩展方程
L n = L n-1 -1 + k
L n = L n-2 -1 + k -1 + k
如果我们继续扩展它，我们将达到基本条件 L 1，我们知道它是 k
L n = L 1 + ((-1 + k) + (-1 + k) .... n-1 次)
我们知道基本条件 L1 =k
L n = k + ( -1 + k ) * (n - 1)
现在，让我们采用一个四叉树，其中 k =4
L n = 4 + 3 (n - 1)
L n = 4 + 3n - 3
L n = 3n + 1
四叉树中叶子节点的数量=3 * 四叉树中内部节点的数量 + 1
考虑通过细分叶节点来扩展四叉树。该叶节点成为内部节点（叶数减一），并添加四个叶节点。如果之前的内部节点数量为N，则新的内部节点数量为N+1，叶子数量为1 + 3*N - 1 + 4 = 1 + 3*(N+1)。一般陈述之后是归纳。