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

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

我很乐意在这里分享更好的解决方案。

- aviad

---

你说“排列”，但是树中每个节点的位置是否重要？ - Colin D

@Colin D，它确实是概率分布。 - aviad

因此，节点被编号，例如对于x=2的情况，我们有两个简单的树：1->2，2->1。 - Alexey A.

http://www.stringology.org/event/2009/psc09p17_presentation.pdf - Colin D

@Alexey 我认为他只是指拓扑结构，节点本身是相同的（如示例所示）。而左右节点之间的拓扑结构不同。 - brimborium

Answer 1

我认为卡特兰数可以用来计算你的树形结构（参见组合学中的应用部分）。它们是一个众所周知的序列，通常通过以下递推关系定义：

这个递推关系经常出现在有关树或递归结构的枚举问题中，因此已经得到了广泛研究。我链接的维基百科条目提供了许多有用的闭式表达式来计算第n个卡特兰数，即

所有这些公式都适合于代码实现，并且比任何递归方法都要快得多。

- Haile

---

是的，卡特兰数与我的递归匹配：f(0)=1; f(x)=sum(f(y)*f(x-y-1), y=0..(x-1))。 - MvG

你应该发布一些关于卡特兰数的实际信息，并发布它们的公式。根据常见问题解答，仅提供链接的答案是不被赞同的。 - Colin D

Answer 2

好的，就我所看到的，你的解决方案是不正确的，对吗？（对于numOfNodes=4，它返回12而不是14）

直观地说，我会采用递归方法。

1. 使用一个节点作为父节点
2. 对于所有可能的分成两组的情况，为两组分别递归调用该函数
3. 将每个分组的结果相乘并求出所有分组的产品之和
4. 返回总和

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

编辑：正如另一个答案中已经说明的那样：您还可以计算第n个卡特兰数。

- brimborium

---

当你试图将一个序列转化为公式时，整数序列在线百科全书总是一个很好的起点。 - MvG

你能帮我弄清楚为什么 numOfNodes=4 时答案应该是14而不是12吗？我是这样计算的：从最低层（假设它们在树的第4层）到根（第1层）有8种方式，从第3层的叶子到第2层的叶子有4种方式。我没有计算从第2层到第3层的方式，因为它们与从第3层到第2层的方式相同。所以这给了我12...我错过了什么吗？ - Pshemo

在 Colin D 上面提供的 这个 PDF 中，您可以在第6页找到4个节点的所有排列。@Pshemo - brimborium

谢谢。现在我知道我计算错误了，不是我应该计算的 :) - Pshemo

@Pshemo 是的，你错过了第三层有两片叶子的树（有两棵这样的树）。 - brimborium

不仅如此，我不知道相同的模式只能计算一次。这个任务很棘手，我喜欢它 :) - Pshemo

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

- Meisam