java - 如何找到可能的二叉树拓扑排列的数量？

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

我认为加泰罗尼亚数字可以计算你的树（参见关于组合学应用的部分）。它们形成了一个众所周知的序列，通常由这种递归关系定义：

这种递归经常出现在关于树或递归结构的枚举问题中，因此它得到了很好的研究。我链接的维基百科条目为第 n 个加泰罗尼亚数提供了许多有用的封闭式表达式，即

它们都适用于代码实现，并且比任何递归方法都快得多。

Answer 2

好的，据我所知，您的解决方案不正确，对吧？（因为numOfNodes=4它返回 12 而不是 14）

直觉上，我会采用递归方法。

1. 用尽一个节点作为父节点
2. 对于所有可能的划分为两个集合，递归调用两个集合的函数
3. 将每个除法的两组结果相乘，并将所有除法的乘积相加
4. 返回总和

但在实施之前，我会确保没有简单的公式。我没有快速找到一个（这并不意味着没有一个）。

编辑：正如在另一个答案中已经说明的那样：您也可以只计算第 n 个加泰罗尼亚语数。

Answer 3

试试这个递归方法：

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