在一个完整的满二叉树

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