首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
一棵二叉树的前序遍历序列为1234567,则它的中序遍历序列不可能为( )。 Ⅰ.3124567 Ⅱ.1234567 Ⅲ.4135627 Ⅳ.1436572
一棵二叉树的前序遍历序列为1234567,则它的中序遍历序列不可能为( )。 Ⅰ.3124567 Ⅱ.1234567 Ⅲ.4135627 Ⅳ.1436572
admin
2014-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
学硕统考专业
相关试题推荐
下列国家中,最早同新中国建立外交关系的是()
英国发动鸦片战争的主要目的是()。
《吕氏春秋》载:“公作则迟,有所匿其力也;分地则速,无所匿其力也。”这条材料反映的实质问题是()。
“文化大革命”发动的两个纲领性文件是()。
《凡尔赛和约》中,战胜国以何种方式处置德国的全部海外殖民地?()。
科举是一种读书、应考、任官三位一体的选官方法,其中的进士科始创于()。
列举列强在华强占的租借地和势力范围。
唐朝时期,每丁服徭役二十天,是为正役,国家若不需要其服役,则每丁可按照每天交纳绢三尺或布三尺七寸五分的标准,交足二十天的数额以代役,称为()。
以下关于图的说法正确的是()。.I在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O,则该图的拓扑序列必定存在Ⅲ在.AOE网中一定只有一条
某计算机的时钟频率为400MHz,测试该计算机的程序使用4种类型的指令。每种指令的数量及所需指令时钟数(CPI)如下表所示,则该计算机的运算速度是()。
随机试题
Whatdoesthemanhavetobringtotheparty?
按照要求完成下列操作:(1)在桌面建立“学生”文件夹。(2)在“学生”文件夹下建立“成绩”、“英语”、“数学”和“语文”4个子文件夹。(3)将“英语”、“数学”和“语文”文件夹复制到“成绩”文件夹中。(4)将“成绩”文件夹中的“英语”、“数学”和“
下列哪些情况下促甲状腺激素分泌增多?
确诊妊娠期糖尿病的实验室检查是
某企业2009年度全年发生下列业务:(1)采用以货换货方式进行商品交易签订合同两份,一份标明价值,自身商品价值50万元,对方商品价值55万元;另一份未标明价值,只列明用自身10吨的商品换对方9吨的商品,经核实自身商品市场单价10000元/吨,对方商
下列各项中应征收契税的是()。
以下程序用来统计文件中字符的个数。请填空。#include“stadio.h”main(){FILE*fp;longnum=0L;if((fp=fopen(“fname.dat”,“r”))==NULL);
"CBSNewsRevampsWebSite,AddingCriticalBlogandVideos"AspartofanambitiousattempttoreviveCBSNews.comwithabr
Whenwasthecustomersurveyconducted?Itwasconducted______.
Spaceisadangerousplace,notonlybecauseofmeteors(流星)butalsobecauseofraysfromthesunandotherstars.Theatmosphere
最新回复
(
0
)