2. 考研
  3. 某二叉树结点的中序序列为BDAECF，后序序列为DBEFCA，则该二叉树对应的森林包括( )棵树。

某二叉树结点的中序序列为BDAECF，后序序列为DBEFCA，则该二叉树对应的森林包括( )棵树。

admin2019-12-10  39
问题 某二叉树结点的中序序列为BDAECF，后序序列为DBEFCA，则该二叉树对应的森林包括(    )棵树。
选项 A、1
B、2
C、3
D、4
答案C
解析 考查由遍历序列确定二叉树、森林与二叉树的转换。根据后序序列，A是二叉树的根结点。根据中序遍历序列，则二叉树的形态一定如下图左所示。对于A的左子树，由后序序列可知，因为B比D后被访问，因此，B必为D的父结点，又由中序序列可知，D是B的右儿子。对于A的右子树，同理可确定结点E、C、F的关系。此二叉树的形态如下图右所示。

    再根据二叉树与森林的对应关系。森林中树的棵数即为其对应二叉树(向右上旋转45°后)中根结点A及其“右兄弟”数。可知此森林中有3棵树，根结点分别为A、C和F。
转载请注明原文地址:https://www.kaotiyun.com/show/Gh3i777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)