Python程序：计算具有n个节点的BST数量

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

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

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

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

• 定义一个函数ncr()。这将需要n, r。
• res := 1
• 如果r > n - r，则
  • r := n - r
• 对于i in range 0 to r - 1，执行：
  • res := res *(n - i)
  • res := floor of (res/(i + 1))
• 返回res
• 从主方法中执行以下操作：
• c := ncr(2 * n, n)
• 返回floor of 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))

输入

3

输出

5

Arnab Chakraborty

更新于：2021年10月12日

246 次浏览

开启您的职业生涯

完成课程获得认证

开始学习