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

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

admin2017-11-20  38
问题 一棵二叉树的前序遍历序列为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，故前序遍历和中序遍历一样。
    (2)当没有右子树时，前序遍历变成tl，中序遍历却变成了lt，故前序遍历和中序遍历不一样。
    综上分析，只要该二叉树没有左子树都能够满足前序遍历和中序遍历是一样的，故Ⅱ是可能的。
    Ⅲ：和Ⅰ的情况一样的分析，前序应该是以14开头，所以不可能是中序序列。
    Ⅳ：构造的二叉树如图8-6所示。

    因此，Ⅰ、Ⅲ不可能。
转载请注明原文地址:https://www.kaotiyun.com/show/UVRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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