题11

题11

题目

某二叉树结点的中序序列为 ,后序序列为 ,则该二叉树对应的森林包括 ( ) 捰树.
A. 1
B. 2
C. 3
D. 4

分析

中序和后序可以唯一确定一个树，画出来这个树以后，再用对应的方法把这个二叉树转化为森林
二叉树转化为森林是，右右孩子找祖宗，父子再断绝关系

解

C
根据二叉树的前序序列和中序序列可以确定一棵二叉树。根据后序序列, 是二叉树的根结点。
根据中序序列,二叉树的形态如下图(a)所示。
对于 的左子树,根据后序序列, 比 后被访问,因此 必为 的父结点,又根据中序序列, 是 的右儿子。对于 的右子树, 同理可确定结点 的关系。
此二叉树的形态如下图(b)所示。

再根据二叉树与森林的对应关系,森林中树的棵数即为其对应二叉树 (向右上旋转 后) 的根结点 及其右兄弟数,或解释为: 对应二叉树从根结点 开始不断往右孩子访问,所访问到的结点数。可知此森林中有 3 棵树,根结点分别为 和 。