2. 考研
  3. 某二叉树的先序序列和后序序列正好相反，则该二叉树可能是( )。 Ⅰ．空或只有一个结点 Ⅱ．任意一个结点无右孩子 Ⅲ．任意一个结点无左孩子

某二叉树的先序序列和后序序列正好相反，则该二叉树可能是( )。 Ⅰ．空或只有一个结点 Ⅱ．任意一个结点无右孩子 Ⅲ．任意一个结点无左孩子

admin2019-12-10  71
问题 某二叉树的先序序列和后序序列正好相反，则该二叉树可能是(    )。
    Ⅰ．空或只有一个结点    Ⅱ．任意一个结点无右孩子    Ⅲ．任意一个结点无左孩子
选项 A、只可能为Ⅰ
B、只可能为Ⅱ
C、只可能为Ⅲ
D、Ⅱ、Ⅲ都有可能
答案D
解析 考生一定需要知道做这种题目的正确思路，而不是在草稿纸上随意画一棵二叉树去套答案，因为有些题目是不可能通过举反例来验证的。
    解题思路：首先前序序列和后序序列的遍历顺序分别为TLR(根左右)和LRT(左右根)，然后分以下几种情况：
    (1)假设该二叉树只有一个根结点，此时前序序列和后序序列也算是相反，所以满足题意。但是空树比较特殊，不存在遍历的概念，无法给出解释，记住就行，所以I错误。
    (2)假设任意一个结点无左孩子，则前序的遍历变成TR，后序的遍历变成RT，恰好相反，所以该假设的二叉树成立。
    (3)假设任意一个结点无右孩子，则前序的遍历变成TL，后序的遍历变成LT，恰好相反，所以该假设的二叉树成立。
    综上所述，Ⅱ和Ⅲ都有可能。    提醒：如果此题为单项选择题，假设出现选项二叉树的高度等于结点的个数也是正确答案，因为这个答案把Ⅱ和Ⅲ的情况都包括了。
转载请注明原文地址:https://kaotiyun.com/show/UQ3i777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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