如何推导含n个顶点的满二叉树的正确递推关系？

首先明确严格满二叉树的定义：每个内部节点都恰好有两个子节点的二叉树，这类树的总节点数n必为奇数（因为根节点1个，每个内部节点贡献2个新节点，总节点数公式为 $n=2k+1$，k为内部节点数）。因此：

• 当n为偶数时，不存在这样的满二叉树，即 $B_n=0$
• 当n=1时，只有单个根节点，$B_1=1$

递推关系推导步骤 #

对于n≥3的奇数，我们通过递归分解满二叉树的结构来推导：

1. 固定根节点：任意一棵n个节点的满二叉树，必然以一个节点为根，剩下的n-1个节点分布在根的左、右两个子树中。
2. 子树的约束：由于是满二叉树，根必须有两个子节点，因此左、右子树都必须是非空的满二叉树。设左子树有i个节点，那么右子树的节点数为 $n-1-i$（总节点数减去根节点，再减去左子树节点数）。
3. 合法的子树节点数：左、右子树都是满二叉树，因此i和 $n-1-i$ 都必须是奇数（满足满二叉树的节点数要求）。结合n是奇数的前提，n-1是偶数，因此i取1,3,...,n-2时，$n-1-i$ 也会是奇数（偶数减奇数为奇数）。
4. 组合计数：对于每个合法的i，左子树有 $B_i$ 种构造方式，右子树有 $B_{n-1-i}$ 种构造方式，因此这种情况下的满二叉树总数为 $B_i \times B_{n-1-i}$。将所有可能的i对应的数量求和，就得到n个节点的满二叉树总数：
   $$B_n = \sum_{i=1}^{n-2} B_i B_{n-i-1}$$
   注：当i为偶数时，$B_i=0$，这些项对求和无贡献，因此可以保留原求和范围。

为什么你的递推式错误 #

你之前推导的 $B(n)=2B(n-1)+1$ 不成立，核心原因是：

• n-1是偶数，不存在n-1个节点的满二叉树（$B(n-1)=0$），递推的前提不成立；
• 满二叉树的构造不能通过给n-1个节点的树添加1个节点实现——满二叉树的节点数只能是奇数，每次扩展需要给一个叶子节点添加两个子节点（一次性增加2个节点），且这种扩展方式的计数会出现重复，不符合递归分解的逻辑。

内容的提问来源于stack exchange，提问作者Hajrah Naeem