尋找葉節點的數量

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，這是正確的答案。