首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
假设一棵二叉树的后序遍历序列为DGJHEBIFCA,中序遍历序列为DBGEHJACIF,则其前序遍历序列为______。
假设一棵二叉树的后序遍历序列为DGJHEBIFCA,中序遍历序列为DBGEHJACIF,则其前序遍历序列为______。
admin
2010-02-13
21
问题
假设一棵二叉树的后序遍历序列为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
程序员上午基础知识考试
软考初级
相关试题推荐
某台24个端口的100BASE-Tx交换机,每个端口在半双工通信状态下的最大数据速率为(35)。
(24)技术采用不同频率的信号在同一信道上传输数据。
计算机通过电话网拨号方式上网时,异步传输的字符同步,下列选项(37)的说法是正确的:采用数据位为8位的异步起止方式传输数据时,其效率最高为(38),高级数据链路控制规程(HDLC)是(39)提出的标准;HDLC帧同步标志是(40);HDLC协议为保证帧同步
信号机制是解决进程同步和互斥的有效工具。实现进程间的互斥时,公用变量信号的初值一般设置为(18);实现进程间的同步时,私用变量初值一般设置为(19)。
电子邮件客户端应用程序向邮件服务器发送邮件时使用(40)协议。下面关于 FTP叙述错误的是(41)。因特网上最重要、最基本的服务是(42)。下面描述的不是Internet提供的服务的选项是(43)。
计算机中声音、图形、图像信息都是以文件的形式存储的,它们的文件格式有许多种,可以通过扩展名来识别,常见的文件扩展名有:①BMP ②AIF ③JPG ④WAV ⑤GIF ⑥VOC其中,表示声音文件的有(9),表示图形、
一个A类网络已有60个子网,若还要添加两个新的子网,并且要求每个子网有尽可能多的主机ID,应指定子网掩码为(29)。
以下关于数字签名的叙述中,错误的是(48)。
阅读以下函数说明和C代码,将C程序中(1)~(5)空缺处的内容补充完整。【说明】对给定的字符集合及相应的权值,采用哈夫曼算法构造最优二叉树,并用结构数组存储最优二叉树。例如,给定字符集合{a,b,c,d}及其权值2、7、4、5,可构造如图
阅读以下说明、C函数和问题,将解答写入答题纸的对应栏内。【说明1】函数test_fl(intm,imn)对整数m、n进行某种运算后返回一个整数值。【c函数1】inttest_f1(intm,intn){intk;k=m>
随机试题
A.温脾汤B.黄龙汤C.济川煎D.新加黄龙汤热结里实,气阴不足证,宜选
A.抑制血管紧张素Ⅱ生成B.抑制血管紧张素与受体结合C.阻止钙离子进入心肌细胞及血管壁平滑肌细胞,使心肌收缩力降低,外周血管扩张D.抑制钠、水重吸收,减少血容量,降低心排血量E.减慢心率,降低心排血量,抑制肾素释放美托洛尔降压的作用机制是
A.向颈部传导B.向上腹部传导C.向心尖部传导D.向左腋下部传导E.向胸骨右缘3~4肋间传导主动脉瓣狭窄的杂音
男性,76岁。结核性心包炎患者。超声心动图显示心包积液。其坐位心界呈
一中年男性患者因急性阑尾炎住院治疗,手术后,主管医生为了使患者尽快恢复健康,给患者使用了一种比较贵的新型抗生素,但并没有同患者商量。患者恢复很快,几天后就可出院。出院时,患者发现自己需付上千元的药费,认为医生没有告诉自己而擅自做主,自己不应该负担这笔钱。在
固定投资估箅的内容按费用的性质划分,包括()。
某大学派出5名志愿者到西部4所中学支教,若每所中学至少有一名志愿者,则不同的分配方案共有:
Manyteenagersthinkthat______canunderstandthembetter.Whichofthefollowingisthewriter’sattitude(态度)?
Whiletheworld’sflufightershaveconcentratedoncounteringtheH1N1swineflu,birdfluH5N1hasquietlycontinuedtotakei
Peoplemightnotenjoysuchasituation:dininginapitch-darkroom,unawarewhat’sonourplatewhilesittingnexttoacomple
最新回复
(
0
)