四叉树有多少片叶子？
How many leaves has a quadtree?
设N为quadtree中的内部节点数。为什么叶子数等于1 + 3 * N？我不明白我们需要争论什么。
考虑通过细分叶节点来扩展四叉树。该叶节点成为内部节点（叶计数减一），并添加四个叶节点。如果之前的内部节点数为N，新的内部节点数为N+1，叶子数为1 + 3*N - 1 + 4 = 1 + 3*(N+1)。归纳后的一般陈述。
TLDR:叶节点数=3*内部节点数+1
我想以@Sneftel 的回答为基础。
设L1,L2,L3指叶数有 1,2,3 个内部节点时的节点。
每当我们添加一个内部节点时，叶节点数的前一个值都会损失 1 个叶节点并增加 k 个叶节点（在 quad k=4 中）。
我们从基本条件开始
L1 = k , 只是根节点k个子节点（四叉树中的k = 4）
例如：
L2 = L1 - 1 + k
L3 = L2 - 1 + k
一般来说，
Ln = Ln-1 -1 + k ，其中 n 是内部节点数， k 是分支因子（四叉树中的 k = 4）
让我们展开方程式
Ln = Ln-1 -1 + k
Ln = Ln-2 -1 + k -1 + k
如果我们继续扩展它，我们将达到基本条件 L1，我们知道它是 k
Ln = L1 + ((-1 + k) + (-1 + k) 。 ... n-1 次)
我们知道基础条件L1=k
Ln = k + ( -1 + k ) * (n - 1)
现在，让我们采用四叉树，其中 k = 4
Ln = 4 + 3 (n - 1)
Ln = 4 + 3n - 3
Ln=3n+1
四叉树中的叶节点数= 3 * 四叉树中的内部节点数 + 1
设N为quadtree中的内部节点数。为什么叶子数等于1 + 3 * N？我不明白我们需要争论什么。
考虑通过细分叶节点来扩展四叉树。该叶节点成为内部节点（叶计数减一），并添加四个叶节点。如果之前的内部节点数为N，新的内部节点数为N+1，叶子数为1 + 3*N - 1 + 4 = 1 + 3*(N+1)。归纳后的一般陈述。
TLDR:叶节点数=3*内部节点数+1
我想以@Sneftel 的回答为基础。
设L1,L2,L3指叶数有 1,2,3 个内部节点时的节点。
每当我们添加一个内部节点时，叶节点数的前一个值都会损失 1 个叶节点并增加 k 个叶节点（在 quad k=4 中）。
我们从基本条件开始
L1 = k , 只是根节点k个子节点（四叉树中的k = 4）
例如：
L2 = L1 - 1 + k
L3 = L2 - 1 + k
一般来说，
Ln = Ln-1 -1 + k ，其中 n 是内部节点数， k 是分支因子（四叉树中的 k = 4）
让我们展开方程式
Ln = Ln-1 -1 + k
Ln = Ln-2 -1 + k -1 + k
如果我们继续扩展它，我们将达到基本条件 L1，我们知道它是 k
Ln = L1 + ((-1 + k) + (-1 + k) 。 ... n-1 次)
我们知道基础条件L1=k
Ln = k + ( -1 + k ) * (n - 1)
现在，让我们采用四叉树，其中 k = 4
Ln = 4 + 3 (n - 1)
Ln = 4 + 3n - 3
Ln=3n+1
四叉树中的叶节点数= 3 * 四叉树中的内部节点数 + 1