用 Python 编写一个程序来计算具有 n 个节点的 BST 的数量

pythonserver side programmingprogramming更新于 2025/12/24 13:00:17

假设我们有 n 个不同的节点。所有节点都是不同的。我们必须找出有多少种排列方式可以将它们排列成二叉搜索树。我们知道，对于二叉搜索树，左子树总是保存较小的值，而右子树保存较大的值。

为了解决这个问题，我们将找到 Catalan 数。Catalan 数 C(n) 表示具有 n 个不同键的二叉搜索树。公式如下

$$C(n)=\frac{(2n)!}{(n+1)!\times n!}$$

因此，如果输入为 n = 3，则输出将为 5，因为

为了解决这个问题，我们将遵循以下步骤 −

定义一个函数 ncr() 。这将需要 n, r
res := 1
if r > n - r，然后
- r := n - r
对于 0 到 r - 1 范围内的 i，执行
- res := res *(n - i)
- res := floor of (res/(i + 1))
返回 res
从主方法，执行以下操作
c := ncr(2 * n, n)
返回 c /(n + 1) 的下限

示例

让我们看看下面的实现以便更好地理解 −

from math import factorial

def ncr(n, r):
   res = 1
   if r > n - r:
      r = n - r

   for i in range(r):
      res *= (n - i)
      res //= (i + 1)

   return res

def solve(n):
   c = ncr(2 * n, n)
   return c // (n + 1)

n = 3
print(solve(n))