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

正文

请到「今天看啥」查看全文

1. 问题描述

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

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

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

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

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

2.问题解析

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

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

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

问题一 解析：为方便理解，设 n=4 ，按照栈的进、出栈限制（后进先出）及编号为 i （

请到「今天看啥」查看全文