CSP-S 提高级 · CSP 2026 提高级第一轮 第 12 题

【单选】含 6 个结点的不同形态的二叉树共有多少棵（结点不带标号，区分左右子树）（ ）。

"不带标号、区分左右子树"的二叉树就是卡特兰数：n 个结点的形态数为 Cₙ = 1/(n+1)·C(2n, n)。n = 6 时 C₆ = 132。

用 C(2n,n) 而忘记除以 (n+1)（得 924）；或者误当成"带标号的二叉树"（那要再乘 6!）。

解析

本题考查卡特兰数的经典应用场景。

为什么是卡特兰数

设 f(n) 为"n 个结点、区分左右子树的不带标号二叉树"的形态数。枚举根结点左子树的结点数 i（0 ≤ i ≤ n−1），则右子树有 n−1−i 个结点：

f(n) = Σ_{i=0}^{n−1} f(i) · f(n−1−i)， f(0) = 1

这正是卡特兰数的递推定义，故 f(n) = Cₙ = 1/(n+1) · C(2n, n)。

代入 n = 6

C₆ = 1/(6+1) × C(12, 6) = 1/7 × 924 = 132

答案 C。

用递推表交叉验证

（可用递推式 Cₙ = Cₙ₋₁ · 2(2n−1)/(n+1) 逐项算：42 → 42×2×11/7 = 132 ✓）

其他选项为什么错

• D. 720 = 6!，这是"带标号"的链状二叉树数量（每个结点做一次左右选择），或 6 个不同元素的排列数，与本问无关；
• A. 42 = C₅，少算了一个结点；
• B. 429 = C(2n,n)/(n+1) 算错或取了 C₇ 附近的值。

卡特兰数的高频出现场景（务必记住）

1. n 个结点的不同二叉树形态数； 2. n 对括号的合法匹配数； 3. 栈的出栈序列数（n 个元素）； 4. 不含交叉的凸多边形三角剖分数； 5. 从 (0,0) 走到 (n,n) 且不越过对角线的路径数。

看到这些字眼，直接套 Cₙ = C(2n,n)/(n+1)。

记忆点

• 带标号的二叉树：n 个不同结点组成的二叉树有 n! · Cₙ 种；
• Cₙ 数值序列：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862 —— 至少背到 132。