Python程式：計算具有n個節點的BST數量

假設我們有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
  • 對於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

更新於：2021年10月12日

246 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告