解析“数据结构”课程中出现的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时的42种可能的出站序列可以这样生成

定义T(0)=1，设T(n)表示编号为1，2，……，n的n辆火车顺序进入栈式结构站台得到的可能出站方式的个数，易知T(1)=1，从n=4和n=5的可能出站方式的规律发现（由1可能出现的位置分类），T(n)是下述递归方程的解：

T(n)=T(0)*T(n-1) +T(1)*T(n-2)+T(2)*T(n-3)+……+T(n-2)*T(1)+T(n-1)*T(0)

问题二和问题三是同一问题的两种不同表现形式，事实上，给定一棵二叉树，将a₁，a_2，……，a_n与二叉树的结点对应，存在前序序列为a₁，a_2，……，a_n的唯一一种对应关系，如下图所示，n=3的5棵不同形状的二叉树正好对应前序序列为a₁，a_2，……，a_n的5种不同的二叉树。

          图1.  3个结点的5棵不同形状的二叉树

 图2. 前序序列为a₁a₂a₃的5棵不同的二叉树

用T(n)表示前序序列为a₁，a_2，……，a_n的二叉树的个数，显然a₁为根结点，a₁的左子树上可能有0～n-1个结点，对应的a₁的右子树分别有n-1～0个结点，根据乘法性质：

T(n)= T(0)*T(n-1) +T(1)*T(n-2)+T(2)*T(n-3)+……+T(n-2)*T(1)+T(n-1)*T(0)

3.递归方程求解

  这里用生成函数（或称为母函数）的方法求解递归方程。构造生成函数

则

由递归方程及上述二式易得

解得

因

故

作者：熊岳山，国防科技大学计算机系教授。

《横扫offer---程序员招聘真题详解700题》，开点工作室著，清华大学出版社出版，天猫、京东等各大网上书店及实体书店均有发售。