🏷️ 知识点：卡特兰数

先序序列为 a,b,c,d 的不同二叉树的个数是（）。

入栈出栈序列 卡特兰数

A. 13 B. 14 C. 15 D. 16

[tag_link] 正确答案：B本题考察 卡特兰数 。根据二叉树前序遍历和中序遍历的递归算法中递归工作栈的状态变化得出：前序序列和中序序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序。因为前序序列和中序序列可以唯一地确定一棵二叉树，所以题意相当千“以序列 a, b, c, d 为入栈次序，则出栈序列的个数为多少“，对于 n 个不同元素进栈，出栈序列的个数$(n+1)/C_{2n}^n$=14。

含有 4 个元素值均不相同的结点的二叉排序树有（ ）种。

A. 4 B. 6 C. 10 D. 14

二叉排序树 卡特兰数

[tag_link]

正确答案：D

二叉排序树（BST）的结构数量由卡特兰数决定。 对于 n 个值均不相同的节点，不同形态的二叉排序树数量等于第 n 个卡特兰数

$C_n$ ，计算公式为

$$C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right),$$

其中 $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ 表示组合数。

当

$n=4$ 时，计算 $C_4$ ：

$$C_4=\frac{1}{5}\left(\genfrac{}{}{0ex}{}{8}{4}\right)=\frac{1}{5}\times 70=14.$$

因此，含有 4 个元素值均不相同的结点的二叉排序树共有 14 种。