N个关键字可以创建的二叉搜索树的可能数量由第N个卡特兰数给出。为什么？

Question

这个问题困扰我已经有一段时间了。我知道，如果给定N个键以二叉搜索树的形式排列，可以创建的可能树的数量对应于卡特兰数列中的第N个数字。

我一直在试图确定为什么会这样; 无法找到任何尝试直观解释它的东西，我求助于SO的集体知识。我发现了其他计算可能树的数量的方法，但它们似乎不太直观，并且没有提供除如何使用它之外的解释。此外，维基页面（上面的链接）甚至显示了具有3个键的可能树形成的图像，这使我认为有一个漂亮而整洁的解释可以被听到（需要注意的是，文章中没有包含）。

提前感谢！

- Sergio Morales

---

非常有趣的问题，虽然我不确定它是否真正与编程有关 :-/ 看起来更像是一个抽象数学（拓扑）问题。 - David Z

我想知道如何确定在给定节点数N的情况下可能创建的二叉搜索树数量。我发现这个问题的答案与询问“Catalan序列的第N个数字是多少？”相同，但即使那个维基百科文章上有公式，我也想要一个解释它为什么有效的解释。我不想接受没有一些内部逻辑或基本直观描述的方法，仅有一个公式。 - Sergio Morales

这适用于二叉树的通用性，与搜索树的细节无关。 - starblue

@starblue：你非常错误。 - Eli Bendersky

仅供参考 - 相关链接：http://codingworkout.blogspot.com/2014/08/all-possible-paranthesis.html - Dreamer

Answer 1

由于您引用的维基百科文章中有四个证明，因此似乎您并不寻求对Catalan数与二叉树排列之间对应关系的数学解释。

因此，以下是两种直观地展现Catalan序列（1、2、5、14、42、...）在组合系统中如何出现的方法。

将多边形切割成三角形

对于一个具有N个边的多边形，您可以在顶点之间画多少条线段，以将整个多边形切分为三角形？

• 三角形（N=3）：1（它已经是一个三角形了）
• 正方形（N=4）：2（可以在任一对角线处切割）
• 五边形（N=5）：5（从一个顶点开始画两条线段。可选择五个顶点）
• 六边形（N=6）：14（尝试画一下）
• ......等等。

在网格中绘制路径而不交叉对角线

在这种情况下，唯一路径的数量就是Catalan数。

2x2网格=> 2条路径

  _|       |
_|       __|

3x3网格 => 5条路径

    _|       |       _|         |         |
  _|      _ _|      |          _|         |
_|      _|       _ _|      _ _|      _ _ _|

4x4网格 => 14条路径
5x5网格 => 42条路径

等等。

如果您尝试为给定的N绘制可能的二叉树，您将看到树排列的方式完全相同。

您不仅仅是盲目接受树和序列之间的对应关系的愿望是令人钦佩的。不幸的是，如果不涉及二项式数学，很难进一步讨论这个问题（并解释为什么Catalan公式“恰好是”它的样子）。如果您想更深入地了解组合数学（包括排列计数）本身，则维基百科上二项式系数的讨论是一个很好的起点。

- ire_and_curses

---

来自一位“数学无神论者”的好回答。http://www.flickr.com/photos/99706190@N00/1869299/ - CmdrTallen

Answer 2

catalan http://www.nohre.se/publicImages/catalan.png

通过按照先序遍历访问所有节点，可以对任何二叉搜索树进行编码，并为每个父节点编码1，为每个叶子节点编码0。如果树具有n个父节点，则将具有n+1个叶子节点，因此二进制代码将具有n个1和(n + 1)个0。此外，任何前缀的代码至少具有与其0相同数量的1。因此，可能的树的数量等于对角线下方路径的数量。

- ragnarius

---

如果你不能证明树与它们的二进制编码之间存在一一对应关系，那么你的论点是没有用的。 - Alexandru

嗯，你在示例中使用了前序遍历！ - Paggas

Answer 3

这里是递归解决方案来计算树的数量...

int countTrees(int numkeys){

if(numkeys > 1){
    int i =1;
    int sum=0;

    for(i = 1; i <= numkeys; i++){

        int lcount = countTrees(i-1);
        int rcount = countTrees(numkeys-i);
        sum += lcount*rcount;
    }
    return(sum);
}else
    return(1);
}

- Sid

Answer 4

我也有同样的渴望想知道为什么它恰好是卡特兰数；现在先不要考虑卡特兰数是什么，找出计算n个节点的唯一二叉树数量的公式。

设C(n)为给定n个顶点的可能二叉树数量，其中C(0)=1，现在考虑当n>0时的C(n)，因为每个二叉树都必须有一个根节点，所以问题现在变成了我们可以在根节点的左右子树上生成多少个可能的二叉树，这些子树共有n-1个顶点。

为了找到答案，我们必须枚举两侧所有可能的树。

C(n) = C(0) * C(n - 1) + C(1) * C(n - 2) + ... + C(n – 2) * C(1) + C(n - 1) * C(0)

这就是卡特兰数的递归形式。一旦我看到这个递归形式，就很容易接受它，而不是维基百科上的公式。

（大部分文本来自https://coldfunction.com/mgen/p/3r）

- user1532146