首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
假设一棵二叉树的后序遍历序列为DGJHEBIFCA,中序遍历序列为DBGEHJACIF,则其前序遍历序列为______。
假设一棵二叉树的后序遍历序列为DGJHEBIFCA,中序遍历序列为DBGEHJACIF,则其前序遍历序列为______。
admin
2010-02-13
20
问题
假设一棵二叉树的后序遍历序列为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
程序员上午基础知识考试
软考初级
相关试题推荐
某演示文稿在演示时,需要从第3张幻灯片直接跳转到第6张幻灯片,那么,应在第3张幻灯片上添加(19),并对其进行相关设置。
若FTP地址写为ftp://123:213@222.18.8.241,则该地址中的"123"的含义是FTP服务器的(59):若FTP地址为ftp://222.18.8.241,则该地址对应连接的FTP服务器用户名字为(60)。
某单位为了扩展局域网新买了一个有3个端口的网桥,扩展后网桥的连接如图10-2所示,端口1与网段A相连,端口2与网段B相连,端口3与网段C相连,网段A中的主机H1的MAC地址是MAC1,网段C中的主机H2的MAC地址是MAC2。则该网桥在工作的过程中,下列说
若Web站点是基于ⅡS建设,而且Web站点内容位于NTFS分区时,有4种方法可以限制用户的访问权限。下列不是限制用户的访问权限的方法是(59)。
下列选项(48)不是标记<FRAME>的属性。
二进制数11001100为源码时,代表的真值为(7);若它是补码,则代表的真值为(8):十进制数-1的补码用8为二进制表示为(9)。
采用SMTP协议和POP协议的服务器功能都是通过Internet实现邮件通信,它们在功能上的区别是(53)。
在寄存器间接寻址中,若指令指定的寄存器是BX,SI,或者DI,则默认操作数存放在(46)段中。这时要用寄存器(47)的内容作为段地址。对于指令MOV BX,[SI]。假设数据段寄存器DS=1000H,代码段寄存器CS=4000H,堆栈段寄存器SS=7000
频分复用的特点是(42),时分复用的特点是(43),波分复用技术中使用的通信介质是(44)。
宽带广域网络可采用(54)技术实现,其骨干网应选用(55)作为主要通信介质,节点之间的连接不宜采用(56)结构。
随机试题
境外生产的药品在中国境内上市销售的注册申请为()
外墙面砖镶贴的开始部位应是()。
FIDIC通用条件给予承包商延长工期的理由有( )。
下列说法中,符合《公司法司法解释(三)》有关规定的有()。
在Excel工作表单元格中,输入()是错误的。
一般塑在天王殿的佛像有()。
陈述性知识的运用不包括()。
电话拨号连接是计算机个人用户常用的接入因特网的方式。称为“非对称数字用户线”的接入技术的英文缩写是___________。
Withthebreakneckspeedatwhichtoday’sbusinessesmove,there’sonemantrawe’dalldowelltoremember;Changeisconstant.
It’sabouttimewe______pouringwastewaterintotheriver.
最新回复
(
0
)