解析“数据结构”课程中出现的Catalan数

戳上面的蓝字“开点工作室”关注我们哦

1. 问题描述

学生在学习数据结构课程时，会遇到或思考下述三个问题：

问题一： 编号为 1 ， 2 ， …… ， n 的 n 辆火车顺序开进栈式结构的站台，问有多少种不同的出站的方式？

问题二： 有多少棵不同的二叉树，前序序列同为 a ₁ ， a _{2 ，} …… ， a _n ？

问题三： n 个结点的不同形状的二叉树有多少棵？

针对初学者学习时的困惑，作者将多年的教学体会总结如下，供学习者参考.

2.问题解析

这三个不同问题看似没有关联，但它们的解是同一个，即著名的 Catalan 数

， Catalan 数是组合数学中一个常出现在各种计数问题的数列，以比列时的数学家欧仁 . 查理 . 卡特兰（ 1814-1894 ）的名字来命名。

现对上述数据结构中的三种计数问题解析如下：

问题一 解析：为方便理解，设 n=4 ，按照栈的进、出栈限制（后进先出）及编号为 i （ i=1 ， 2 ， 3 ， 4 ）的火车都有进栈立即出栈或进栈后不立即出栈两种状态，编号为 1 ， 2 ， 3 ， 4 的 4 辆火车顺序开进栈式结构的站台，共有 14 种不同的出栈式结构站台的方式，即 n=4 的 Catalan 数为 14 ，对应可能的出站序列分别为：

上述 14 种出站序列可以改写为：

完全类似地， n=5 时的