寻找叶节点的数量

Question

N元树对于每个节点有N个子节点。如果树有M个非叶节点，如何找到叶节点的no？

Answer 1

首先，如果根级别为0，那么该树的K级将具有N^K节点。您可以逐级开始递增计数器，直到获得M节点。通过这种方式，您会发现树由多少个层构成。并且叶节点的数量是最后一级上的节点数量 - 它是N^lastLevel。

下面是一个例子：N = 3, M = 4。

First level = 3^0 = 1 
Second level = 3^1 = 3 
1 + 3 = 4 

所以我们发现树有两个级别（从0开始计数）。 答案是3^2 = 9。

注意：您也可以直接找到层数，通过注意到M是几何级数的总和：1 + 3 + 9 + 27 ... = M

希望这是显而易见的。

Answer 2

从数学上讲，节点的几何级数增加。

第0级 - 1
第一级 - N的
第二级 - N^2
第三级 - N的^ 3
.... 第m个水平 - N R个米

所以总第m级节点的数目为1 + n + n^2 + .. + n^m-1。 （1-n ^（m + 1））/（1-n ^（m + 1））+ 1^n），我们称这个数量为K.

现在我们需要的是叶节点的数量是n^m，我们得到的是K.即非叶节点的总数。做一些数学公式调整你会发现
N R个M = K *（N-1）+ 1

例如可以说在三元树中非叶节点的总数是40，然后使用这个公式可以得到叶节点的总数为81，这是正确的答案。