问题分析

考虑所有 $n$ 个结点的不同构有根二叉树，每种形态等概率出现，求叶子节点数的期望值。

关键结论

对于 $n$ 个结点的有根二叉树，叶子节点数的期望为：

$$E_n = \frac{n(n+1)}{2(2n-1)}$$

推导思路

1. 二叉树计数

$n$ 个结点的不同构有根二叉树的数量由卡特兰数 $C_n$ 给出：

$$C_n = \frac{1}{n+1}\binom{2n}{n}$$

2. 叶子节点特征

在二叉树中，每个非叶子节点都有 $2$ 个子节点（可能为空）。通过生成函数或组合分析可以证明：

所有 $n$ 结点有根二叉树的叶子节点总数为 $\binom{2n-2}{n-1}$

3. 期望计算

叶子节点的期望数为：

$$E_n = \frac{\text{叶子节点总数}}{\text{二叉树总数}} = \frac{\binom{2n-2}{n-1}}{C_n} $$

代入卡特兰数公式：

$$E_n = \frac{\binom{2n-2}{n-1}}{\frac{1}{n+1}\binom{2n}{n}} = \frac{(n+1)\binom{2n-2}{n-1}}{\binom{2n}{n}} $$

利用组合恒等式化简：

$$\frac{\binom{2n-2}{n-1}}{\binom{2n}{n}} = \frac{n(n+1)}{2(2n-1)} $$

因此：

$$E_n = \frac{n(n+1)}{2(2n-1)}$$

算法实现

根据推导的公式直接计算：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    double result = 1.0 * n * (n + 1) / (2 * (2 * n - 1));
    cout << setprecision(9) << fixed << result << endl;
    return 0;
}

复杂度分析

时间复杂度：$O(1)$，仅需常数次算术运算 空间复杂度：$O(1)$，只使用常数额外空间

样例验证

当 $n = 1$ 时：

$$E_1 = \frac{1 \times 2}{2 \times (2 \times 1 - 1)} = \frac{2}{2 \times 1} = 1.0 $$

与题目样例输出一致。

数值特性

当 $n = 1$ 时，$E_1 = 1.0$ 当 $n \to \infty$ 时，$E_n \sim \frac{n}{4}$ 对于较大的 $n$，约 $25\%$ 的节点是叶子节点

总结

本题通过组合数学方法推导出有根二叉树叶子节点数的期望公式，实现时直接套用公式计算即可。算法高效且精度满足题目要求 $10^{-9}$ 的误差范围。