有多少片叶子有四叉树？

Question

让N为quadtree内部节点的数量。为什么叶子的数量等于1 + 3 * N？我不明白我们需要争辩。

Answer 1

考虑通过细分叶节点来扩展四叉树。该叶节点成为内部节点（将叶数减1），并添加四个叶节点。如果以前的内部节点数为N，则新的内部节点数为N + 1，树叶数为1 + 3 * N-1 + 4 = 1 + 3 *（N + 1）。一般性声明如下归纳。