BCSP-X · 2024 BCSP-X 上半年活动基础知识测评（初中组） 第 15 题

5 个没有区别的结点构成不同形态的二叉树的种类有（ ）个。

别急着背公式，先想卡特兰数怎么来的。n个不同节点的二叉树形态数就是卡特兰数C_n，这里n=5，直接套公式算出结果，再和选项比对。

最容易栽跟头的是把‘不同形态’理解成‘不同排列’，或者误以为二叉树节点有区别。这题特意强调‘5个没有区别的结点’，就是告诉你别管节点标号，只看树的结构。还有人会混淆完全二叉树的叶子数公式，或者背错卡特兰数递推式，导致算出30、35、40这些接近的数。其实只要记住卡特兰数C_n = (2n)! / ((n+1)! n!)，或者用递推C_0=1, C_{n+1}=sum(C_i*C_{n-i})，手算5步就能稳稳得到42。

这道题考的是二叉树的形态计数，核心就是卡特兰数（Catalan number）。命题人喜欢在这种单选题里挖‘节点是否可区分’的坑——如果节点有标号，那5个节点能排出的二叉树数量会巨大得多；但题目明确说‘没有区别的结点’，所以只统计结构不同的树，这就是卡特兰数的经典应用场景。

先回顾概念：一个二叉树的形态，只看左子树和右子树的形状组合，跟节点标号无关。对于n个节点，设f(n)为不同形态数。根节点占1个，剩下n-1个节点要分给左子树和右子树。假设左子树有i个节点，右子树就有n-1-i个。左子树的形态有f(i)种，右子树的形态有f(n-1-i)种，根据乘法原理，这种分配方式贡献f(i)*f(n-1-i)种树。i可以从0到n-1遍历，于是得到递推式：f(0)=1（空树算一种），f(n)=sum_{i=0}^{n-1} f(i)*f(n-1-i)。这就是卡特兰数的定义。

现在直接套n=5。手算递推：f(0)=1；f(1)=1；f(2)=f(0)f(1)+f(1)f(0)=2；f(3)=f(0)f(2)+f(1)f(1)+f(2)f(0)=5；f(4)=f(0)f(3)+f(1)f(2)+f(2)f(1)+f(3)f(0)=14；f(5)=f(0)f(4)+f(1)f(3)+f(2)f(2)+f(3)f(1)+f(4)f(0)=14+5+4+5+14=42。所以答案是42，对应选项C。

也可以直接用卡特兰数通项公式：f(n)=(2n)!/((n+1)! n!)。代入n=5，(10)!/(6! 5!)=3628800/(720*120)=3628800/86400=42，结果一致。

避坑提醒：别把f(5)算成30或35，那是把递推式里的某一项漏了或者重复加了；也别误以为二叉树节点不同，那样数量会远大于42。完全二叉树的叶子数公式、空指针数这些知识点虽然重要，但跟这道题无关，别被它们带偏。

从考频趋势看，二叉树形态计数在近年信息学竞赛中属于高频考点，卡特兰数及其递推式几乎年年出现，尤其在组合计数类题目里。这类题往往以单选题形式考查基本递推或通项公式，难度中等，但需要准确记忆递推结构，防止在求和时出错。未来命题很可能继续围绕卡特兰数变体出题，比如带限制条件的二叉树计数，或者结合生成函数求通项，但基础形态数本身仍是必考内容。