CSP-S 2026 第一轮 第 12 题：含 6 个结点的不同形态的二叉树共有多少棵（结点不带标号

题目

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

选项

• A. 42
• B. 429
• C. 132
• D. 720

答案

C

题解

选 C. 132。这类“结点不带标号、区分左右子树”的二叉树计数，是卡特兰数问题。

设 \(f(n)\) 表示含 \(n\) 个结点的二叉树形态数，并规定 \(f(0)=1\)（空树算一种）。

确定根结点后，还剩 \(n-1\) 个结点。如果左子树有 \(i\) 个结点，右子树就有 \(n-1-i\) 个，两边的形态可以任意组合，因此： \[ f(n)=\sum_{i=0}^{n-1}f(i)f(n-1-i) \]

依次得到：

于是： \[ \begin{aligned} f(6) &=1\times42+1\times14+2\times5\\ &\quad+5\times2+14\times1+42\times1\\ &=\boxed{132} \end{aligned} \]

也可以直接用卡特兰数公式： \[ f(n)=\frac{1}{n+1}\binom{2n}{n}, \qquad f(6)=\frac17\binom{12}{6}=\frac{924}{7}=132. \]