21

这一直困扰着我一段时间。我知道给定 N 个键以二叉搜索树的形式排列，可以创建的树的可能数量对应于Catalan 序列中的第 N 个数。

我一直在试图确定这是为什么；找不到任何甚至可能试图直观地解释它的东西，我求助于 SO 的集体知识。我找到了其他方法来计算可能的树的数量，但它们似乎不太直观，除了如何使用它之外没有提供任何解释。再加上 wiki 页面（上面的链接）甚至显示了带有 3 个键的可能的树形结构的图像，这让我认为有一个很好的和简洁的解释可以听到（不用说，不包括在文章中）。

提前致谢！

4

4 回答 4

14

由于您引用的维基百科文章中有四个证明，因此您似乎没有在寻找加泰罗尼亚数字与二叉树排列之间对应关系的数学解释。

因此，这里有两种方法可以尝试直观地可视化加泰罗尼亚语序列（1、2、5、14、42，...）如何在组合系统中出现。

将多边形切割成三角形

对于边N的多边形，您可以在将多边形完全切割成三角形的顶点之间绘制切口的方法有多少？

  • 三角形（N=3）：1（已经是三角形）
  • 正方形（N=4）：2（可以在任一对角线上切片）
  • 五边形（N=5）：5（从一个顶点发出的两条切片线。五个顶点可供选择）
  • 六边形 (N=6): 14 (试着画出来)
  • ...等等。

在不穿过对角线的情况下通过网格绘制路径

在这种情况下，唯一路径的数量是加泰罗尼亚数。

2x2 网格 => 2 条路径

  _|       |
_|       __|

3x3 网格 => 5 条路径

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

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

等等。

如果你尝试为给定的 N 绘制可能的二叉树，你会发现树的排列方式是一样的。

您不只是盲目地接受树和序列之间的对应关系的愿望令人钦佩。不幸的是，如果不调用二项式数学，就很难在这个讨论中走得更远（并解释为什么加泰罗尼亚公式“恰好”是这样）。如果您想更深入地了解组合学（包括排列计数）本身，那么维基百科对二项式系数的讨论是一个很好的起点。

于 2009-08-30T12:49:42.570 回答
7

加泰罗尼亚语 http://www.nohre.se/publicImages/catalan.png

任何二叉搜索树都可以通过预先访问所有节点进行编码，并为每个父节点编码一个 1，为每个叶子编码一个 0。如果树有 n 个父节点，它将有 n+1 个叶子，因此二进制代码将有 n 1:s 和 (n+1) 0:s。此外，代码的任何前缀都将具有至少与 0:s 一样多的 1:s。因此，可能的树数等于对角线以下的路径数。

于 2009-09-27T10:50:15.017 回答
2

那么这里是计算树的递归解决方案......

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);
}
于 2010-01-10T03:11:00.940 回答
0

我同样想知道为什么它恰好是加泰罗尼亚数字；暂时忘记加泰罗尼亚数是多少，找出计算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）

于 2021-01-02T04:01:58.213 回答