含有 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 种。