完整和完整二叉树中的平均子代节点数

Question

给定一个包含n个节点的完整二叉树，一个节点的平均后代数是多少？例如，根节点有n-1个子节点，每个叶节点有0个子节点，但是考虑到所有节点，平均值是多少？

Answer 1

让我们暂时改变一下您的问题：我们称之为“后代”是包括节点本身在内的后代数量。

一片叶子有1个后代，它的父母有3个后代，然后是7个，然后是15个，等等。这些数字是2^k-1，其中k是树底部的层数（叶子的k=1）。

对于K级，您的树中显然有2^K-1节点；因为您将此值称为n，所以您有n=2^K-1和K=log2（n 1）。

仍然像我以前所做的那样调用后代（参见稍后的确切问题），2^（K-1）节点（叶子）有1个后代，2^（K-2）节点有3个后代，...直到2^（K-K）=1节点的n个后代。

后代的平均数量为：

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