先序序列为 a,b,c,d 的不同二叉树的个数是（）。

入栈出栈序列 卡特兰数

A. 13 B. 14 C. 15 D. 16

[tag_link] 正确答案：B本题考察 卡特兰数 。根据二叉树前序遍历和中序遍历的递归算法中递归工作栈的状态变化得出：前序序列和中序序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序。因为前序序列和中序序列可以唯一地确定一棵二叉树，所以题意相当千“以序列 a, b, c, d 为入栈次序，则出栈序列的个数为多少“，对于 n 个不同元素进栈，出栈序列的个数$(n+1)/C_{2n}^n$=14。