2. 考研
  3. 一棵二叉树的前序遍历序列为1234567，则它的中序遍历序列不可能为( )。 Ⅰ．3124567 Ⅱ．1234567 Ⅲ．4135627 Ⅳ．1436572

一棵二叉树的前序遍历序列为1234567，则它的中序遍历序列不可能为( )。 Ⅰ．3124567 Ⅱ．1234567 Ⅲ．4135627 Ⅳ．1436572

admin2014-12-08  53
问题 一棵二叉树的前序遍历序列为1234567，则它的中序遍历序列不可能为(    )。
    Ⅰ．3124567    Ⅱ．1234567    Ⅲ．4135627    Ⅳ．1436572
选项 A、仅Ⅰ、Ⅱ
B、仅Ⅱ、Ⅲ
C、仅Ⅰ、Ⅲ
D、仅Ⅰ、Ⅲ、Ⅳ
答案C
解析 由二叉树的前序遍历为1234567可知，该二叉树的根为结点1，并且2为1的孩子结点。
    Ⅰ：假如3124567是该二叉树的中序遍历，那么3必然是1的左孩子，前序遍历的序列一定是13，而前序遍历并没有以13开头，所以Ⅰ不可能是中序序列。
    Ⅱ：首先需要来证明一个知识点：什么情况下，前序遍历和中序遍历是一样的。前序遍历是tlr(根左右)，中序遍历是ltr(左根右)，下面就从tlr和ltr着手。
    (1)当没有左子树时，前序遍历变成了tr，中序遍历也变成了tr，故此种情况F前序遍历和中序遍历一样。    (2)当没有右子树时，前序遍历变成tl，中序遍历却变成了lt，故此种情况下前序遍历和中序遍历不一样。
    综上分析，只要该二叉树没有左子树，则都能够满足前序遍历和中序遍历是一样的，故Ⅱ是可能的。
    Ⅲ：和Ⅰ的情况一样的分析，前序应该是以14开头，所以不可能是中序序列。
    Ⅳ：构造的二叉树如图8-6所示。

    因此，Ⅰ、Ⅲ不可能。
    总结：以下3种情况可以唯一确定一棵二叉树。    ①先序序列和中序序列。    ②后序序列和中序序列。    ③层次序列和中序序列(重点，注意出题。)
转载请注明原文地址:https://kaotiyun.com/show/gdxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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