如何查找可能的二叉樹拓撲排列的數量？

Question

給定數量的二叉樹節點（X）寫入方法，返回X節點的二叉樹隨機排列的數量。

實例：

X = 1：1

 o 

X = 2：2

 o o 
    o  o 

X = 3：5

 o o   o  o  o 
     o  o  o   o o o 
    o   o  o  o 

我結束了：

public static int numOfPerms(int numOfNodes) { 
     if (numOfNodes<=2 && numOfNodes > 0) { 
      return numOfNodes; 
     } 
     int res = 1; 
     for (int i=1; i<=numOfNodes; i++) { 
      res = res*(4*i-1)/(i+1); 
     } 
     return res; 
    } 

我希望在這裏分享更好的解決方案。

Answer 1

試試這個遞歸方法：

static int numOfPerms(int numOfNodes) { 
    if (numOfNodes == 1) { 
     return 1; 
    } 

    numOfNodes = numOfNodes - 1; 
    return ((numOfPerms(numOfNodes) * (2*numOfNodes+2) * 
      (2*numOfNodes+1))/((numOfNodes+1)*(numOfNodes+2))); 
} 

Answer 2

好吧，據我所知，你的解決方案是不正確的，對吧？ （對於numOfNodes=4它返回12而不是14）

直覺上，我會去遞歸方法。

1. 使用了一個節點作爲父節點
2. 所有可能劃分爲兩組，遞歸調用函數的兩套
3. 從兩組各部門的相乘的結果，並總結出的產品所有部門
4. 返回總和

但是實現它之前，我會確保有對此並沒有簡單的公式。我沒有在快速找到一個（這並不意味着沒有一個）。

編輯：如已在另一個答案中所述：你也可以只計算第n個加泰羅尼亞號碼。

Answer 3

我認爲Catalan Numbers可以計算你的樹木（參見關於applications in combinatorics的部分）。它們形成通常由該遞推關係定義一個衆所周知的序列：

這種復發經常出現在約樹或遞歸結構的計數問題，所以這是相當充分的研究。維基百科條目我連接給出了一些用於第n個Catalan數有用封閉形式的表達式，即

所有的人都適合於代碼實現，並且比任何遞歸方法快得多。