题39

题39

题目

Q:【2015 统考真题】先序序列为 的不同二叉树的个数是 ( ).
A. 13
B. 14
C. 15
D. 16

分析

A:问题的关键在于a是根结点，bcd可以组成多少种子树的组合

解

A
根据二叉树前序遍历和中序遍历的递归算法中递归工作栈的状态变化得出: 前序序列和中序序列的关系相当于以前序序列为入栈次序, 以中序序列为出栈次序。因为前序序列和中序序列可以唯一地确定一棵二叉树,所以题意相当于 “以序列 为入栈次序,则出栈序列的个数为? ”,对于 个不同元素进栈,出栈序列的个数为卡特兰数 。