查找叶节点的数量

Question

N元树具有每个节点的N个子节点.如果树有M个非叶节点,如何找到叶子节点的数量？

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

希望很清楚.