首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
假设一棵二叉树的后序遍历序列为DGJHEBIFCA,中序遍历序列为DBGEHJACIF,则其前序遍历序列为______。
假设一棵二叉树的后序遍历序列为DGJHEBIFCA,中序遍历序列为DBGEHJACIF,则其前序遍历序列为______。
admin
2010-02-13
16
问题
假设一棵二叉树的后序遍历序列为DGJHEBIFCA,中序遍历序列为DBGEHJACIF,则其前序遍历序列为______。
选项
A、ABCDEFGHIJ
B、ABDEGHJCFI
C、ABDEGHJFIC
D、ABDEGJHCFI
答案
B
解析
这类题目,可以根据所给条件,还原二叉树,然后再进行前序遍历。还原二叉树的要点是首先确定根结点,再确定左子树的组成结点和右子树的组成结点。然后再针对每个左子树和右子树,继续确定其根结点以及左右子树。重点是,根据后序遍历的特点是,最后一个结点必然为根。中序遍历中,根结点的左边,是左子树的结点,右边是右子树的结点。
分析过程如下:
①首先,根据后序遍历为DGJHEBIFCA,说明这棵二叉树的根为A。再根据中序遍历的结果:DBGEHJACIF,说明DBGEHJ在根结点A的左边,为左子树上的结点。CIF在根结点A的右边,是右子树上的结点。如图8-25所示。
②根据后序遍历结果,DGJHEBIFCA,说明CIF这棵子树上,C是根结点。再根据IF在中序遍历中的位置,可知FI都是其右子树。再根据后序遍历结果,可知, F为根,I是其右结点。如图8-26所示。
③对于DBGEHJ这棵左子树,根据后序遍历结果可知,B是其根结点。再根据中序遍历结果可知,D是其左子树,GEHJ是其右子树。如图8-27所示。
④对于GEHJ这个二叉树,根据后序遍历结果,E为根结点。再根据中序遍历结果,HJ为其右子树。G为其左子树。如图8-28所示。
⑤对于HJ,根据后序遍历结果,H是根,再根据中序遍历结果,J是H的右子树。构成二叉树如图8-29所示。
对此二叉树进行前序遍历的结果是:ABDEGHJCFI。选项B为本题正确答案。
转载请注明原文地址:https://kaotiyun.com/show/3ZjZ777K
本试题收录于:
程序员上午基础知识考试题库软考初级分类
0
程序员上午基础知识考试
软考初级
相关试题推荐
Windows 2003操作系统的活动目录可提供许多优越的管理,它的实现仅需一个存储在中央目录服务器的(57)。
IP地址211.62用二进制表示可以写为(33)。
在Windows资源管理器中,假设已经选定文件,以下关于“复制”操作的叙述中,正确的有(3)。
调制解调器(Modem)的功能是实现(45)。在Internet上,可以利用(46)与网友直接聊天。
下列选项(48)不是标记<FRAME>的属性。
TCP/IP协议集中用来报告差错或提供有关意外情况的信息的协议是(24)。
用来选择被淘汰页面的算法称为页面淘汰算法。在以下算法中,(15)最理想。
根据程序局部性理论,Denning提出了工作集理论。工作集是进程运行时被频繁访问的页面集合。在进程运行时,如果它的工作页面都在(7)内,能够使进程有效地运行,否则会出现频繁的页面调入/调出现象。假设窗口尺寸为10,在某一段时间内,进程所访问的逻辑页面顺序如
下列4条叙述中,有错误的一条是(1)。
随机试题
在反对新老殖民主义、推动非洲和阿拉伯世界的民族独立运动中有着重大影响、曾被称为“革命的布道坛”的非洲规模最大的国际电台是()
初孕,孕41周,临产12小时入院,宫高39cm,估计胎儿3800g,LOA,胎心好,宫缩强,阴道检查:宫颈已展平,开大5cm,胎膜已破,头先露,一1,产瘤5cm×5cm×1.0cm,宫缩时先露下降不明显。应采取何项处理
《出境危险货物运输包装使用鉴定结果单》超过有效期,应及时向检验检疫机构申请换证手续。()
实物资产投资项目包括()。
应税消费品计税价格明显偏低又无正当理由的,税务机关有权核定其计税价格。下列应税消费品应由国家税务总局核定其计税价格的有()。
甲国居民A在乙国收入100万元,甲乙两国的所得税税率分别为20%和15%,两国均实行属人兼属地税收管辖权,甲国对境外两国实行抵免法,A应向甲国缴纳所得税()万元。
要求列出计算步骤,每步骤运算得数精确到小数点后两位张某在市区内开办了一家餐馆和一个副食加工店,均为个人独资。2010年初,自行核算餐馆2009年度销售收入为400000元,支出合计360000元,副食加工店2009年度销售收入为800000元,支出合计
在高架桥上用绳子测量高架桥的高度,把绳子对折垂到地面时尚余10米,把绳子三折垂到地面时尚余2米,则高架桥高度和绳长分别是:
有时为了医治一些危重病人,医院允许使用海洛因作为止痛药。其实,这样做是应当被禁止的。因为,毒品贩子会通过这种渠道获取海洛因,对社会造成严重危害。以下哪项如果为真,最能削弱以上的论证?
WhatCanWeLearnfromArt?I.IntroductionA.Differencebetweengeneralhistoryandarthistory—Focus:—generalhistory:【T1
最新回复
(
0
)