单选题 一棵二叉树的前序遍历序列为1234567,它的中序遍历序列可能是______。
【正确答案】 B
【答案解析】[解析] 考查二叉树的遍历序列、由遍历序列构造二叉树。
解法一:由前序序列可知1为根结点,且2为1的孩子结点。选项A,如果中序序列是3124567,则3应为1的左孩子,其前序序列应为13…,错误。选项B,当2为1的右孩子,3为2的右孩子…时,满足题目要求。选项C,类似于选项A,其前序序列应为14…,错误。选项D,2为1的左孩子,3为1的右子树的根,5为3的左子树,647为3的右子树,其前序序列应为1253…,错误。
对于选项B,要知道什么情况下前序序列NLR(根左右)和中序序列LNR是一样的:
①当二叉树没有左子树时,前序序列变成了NR,中序序列也变成了NR,前序序列和中序序列一样。
②当二叉树没有右子树时,前序序列变成了NL,后序序列变成了LN,前序序列和中序序列不一样。
综上分析,当二叉树是一棵向右倾斜的单支树(没有左子树)时,则能够满足该二叉树的前序序列和中序序列相同。
解法二:二叉树前序遍历与中序遍历的关系相当于以前序序列为入栈顺序,以中序序列为出栈顺序的栈,A选项中,3先出栈那么第二个出栈的将是2或者4、5、6、7。不可能为1。同理C、D皆不满足条件。(推荐同学记住这个性质,做到类似的选择题会方便很多,而且更快速)。
解法三:因为前序和中序序列可以确定一颗二叉树,所以可试着用题目中的序列构造出相应的二叉树,即可得知,只有B答案的序列可以构造出二叉树。