题13

题13

题目

若二叉树中结点的先序序列是 ,中序序列是 ,则 ( ) .
A. 结点 和结点 分别在某结点的左子树和右子树中
B. 结点 在结点 的右子树中
C. 结点 在结点 的左子树中
D. 结点 和结点 分别在某结点的两棵非空子树中

分析

首先，先序和中序可以唯一确定一棵树
中序遍历从根结点把序列分为左右两部分
显然先序的根a在中序序列中，比较靠右，把b分为以a为根的左子树上

解

C
先序序列是 ,因此 和 结点的 3 种情况如下图(a) (c)所示。中序序列是 ,因此 和 结点的 3 种情况如下图(d) (f) (f)所示,相同部分是 在 的左子树中。 (b) (f)

(a)