n个不同关键字构成的二叉排序树有多少种

对于n个不同关键字构成的二叉排序树，其形态个数可以用卡塔兰数表示。卡塔兰数是一个数列，其前几项为：

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ...

其中第n项表示n个节点的二叉排序树的形态个数。

具体的计算方法为：

假设有n个不同的关键字，我们可以先任选一个关键字作为根节点，然后将剩余的n-1个关键字分别分成两部分，一部分小于根节点，一部分大于根节点。这样就可以得到两个子问题，分别是左子树和右子树的形态个数。使用递归的方式，将左子树和右子树的形态个数相乘，就可以得到n个节点的二叉排序树的形态个数。

具体的公式为：

C(n) = C(0)C(n-1) + C(1)C(n-2) + ... + C(n-1)C(0)

其中C(n)表示n个节点的二叉排序树的形态个数，C(0)=1表示空树的形态个数为1。

例如，当n=4时，有4个不同关键字构成的二叉排序树的形态个数为：

C(4) = C(0)C(3) + C(1)C(2) + C(2)C(1) + C(3)C(0) = 15 + 12 + 21 + 51 = 14

因此，有4个不同关键字构成的二叉排序树的形态个数为14个