满K叉树的叶子节点数有什么特点？

满 K 叉树中的节点要么是叶子结点，要么有 $k$k 个子节点

满 K 叉树的叶子结点数 $m$m 满足：
$(m-1) \% (k-1) = 0$(m−1)%(k−1)=0

以3叉树为例:

容易观察：假设初始状态如蓝框所示，每当增加新的叶子节点，必然需要把一个叶子结点变成中间节点，再增加新的 $k$k 个叶子结点，所以算下来新增了 $k-1$k−1 个叶子结点。

所以，满 $k$k 叉树的叶子结点数 $m$m 必然是如下等差数列的一项：
$k, 2k-1, 3k-2, \ldots, k+n(k-1), \ldots$k,2k−1,3k−2,…,k+n(k−1),…
即
$m = k + n(k-1)$m=k+n(k−1)$(m-1)\%(k-1) = 0$(m−1)%(k−1)=0

这个结论有什么用呢？看下面这道题：

这道题的本质上就是要添加叶子节点使得归并树是一个满 7-叉树：

假设需要添加 $x$x 个叶子节点，使
$(33-1+x)\%(7-1) = 0$(33−1+x)%(7−1)=0
得出：$x = 4$x=4.