在一個完整的滿二叉樹

Question

給出了完整和充分的二叉樹ň節點的後代節點的平均數量，什麼是後人一個節點的平均數？例如，根節點有n - 1個後代，每個葉節點有0個後代，但考慮到所有節點，平均值是多少？

Answer 1

讓我們改變一點你的問題了片刻：我們所說的「後代」將包括節點本身後代的數量。

葉子有1個後代，它的父代有3個後代，然後是7，然後是15等。這些數字是2^k-1種類，其中k是從樹底部開始的級數（k = 1 fot葉子）。

對於K級別，您的樹中顯然有2^K-1節點;既然你叫這個值n，你有n = 2^K-1和K = log2（n + 1）。你有1^2（K-1）個節點（樹葉）的後代，2 ^（K-2）個節點的3個後代，...直到n^2 ^（KK）= 1個節點的後代。

後代的平均數目將是：

Sum(k=1,K, 2^(K-k) * (2^k-1))/n 

根據你的「後裔」（不包括節點本身）的定義，你必須。減去1：

Sum(k=1,K, 2^(K-k) * (2^k-1))/n - 1 

通過更換K，你得到：

Sum(k=1,log2(n+1), (2^k-1)(n+1)/2^k)/n - 1 

隨着程序Pari-GP，我鍵入：

f(n)=sum(k=1,round(log(n+1)/log(2)), (2^k-1)*(n+1)/2^k)/n - 1 

，我也得到：

f(1)=0 
f(3)=2/3 
f(7)=10/7 
f(15)=34/15 

它看起來像A036799(n)/N。如果序列實際上是相同的（我沒有仔細檢查），則可以寫出更簡單的表達式（沒有總和）：

f(n)= ((log(n+1)/log(2)-2)*(n+1)+2)/n