在Python中计算n个节点的二叉搜索树数量的程序

假设我们有n个不同的节点。它们都是独立的。我们要找出可以排列它们形成二叉搜索树的方式的数量。我们知道对于二叉搜索树，左子树始终持有较小的值，而右子树持有更大的值。

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

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

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

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

• 定义一个ncr()函数，该函数将需要n、r
• res：= 1
• 如果r > n-r，则
  • r：= n-r
• 对于范围从0到r-1的i，循环执行以下操作
  • res：=res*(n-i)
  • res：=res/（i+1）的floor值
• 返回值res
• 在主方法中，执行以下操作
• c：= ncr(2 * n, n)
• 返回c /（n + 1）的floor值

示例

让我们看一下以下实现，以获得更好的理解−

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))

输入

3

输出

5