查找叶节点的数目

首先,如果根是水平的 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 .

注意:您也可以直接找到级别编号,注意 米 是几何级数的总和: 1 + 3 + 9 + 27 ... = M

希望是清楚的。

从数学上讲,节点在几何级数中增加。

零级- 1级
第一级-n
第2级-n^2
第3级-n^3
… MTH水平-N^m

所以m-1级的节点总数是1+n+n^2+。+N^ M-1。

现在有一个很好的公式来计算1+a+a^2+a^3+…+A^M,即 (1-n^(m+1))/(1-n),我们把这个量称为k。

现在我们需要的是叶节点的数量,它是n^m,我们得到的是k,也就是非叶节点的总数。做一些数学公式的调整,你会发现
n^=m= k*(n-1)+1。

例如,假设在三叉树中,非叶节点的总数是40,那么使用这个公式,可以得到叶节点的总数是81,这是正确的答案。