首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设k是中序线索二叉树中一个有左子女的结点,且k不是根结点,则k在中序序列下的直接前驱结点是( )。
设k是中序线索二叉树中一个有左子女的结点,且k不是根结点,则k在中序序列下的直接前驱结点是( )。
admin
2019-12-10
31
问题
设k是中序线索二叉树中一个有左子女的结点,且k不是根结点,则k在中序序列下的直接前驱结点是( )。
选项
A、k的左线索(指示中序前驱)所指示的结点
B、从k父结点的左子女开始沿右子女链走到底的结点
C、从k的左子女开始沿右子女链走到底的结点
D、从k的左子女开始沿左子女链走到底的结点
答案
C
解析
如果k没有左子女,则k的左指针即为指向k的中序前驱的线索;当k有左子女时,k的中序直接前驱结点是k的左子树中中序的最后一个结点,即从k的左子女开始沿右链走到右指针不再是右子女的结点为止,该结点即为k的中序前驱结点。
说明:上述二叉树的线索化算法其实考试中涉及的不多,本节在考试中涉及最多的是,在选择题中给你一棵二叉树,让你指出其中一个结点的线索按照某种线索化方法所应该指向的结点。
例如:请画出图4—7中按照中序线索化方法线索化后E结点的右线索的接连情况。
解决这类题的方法为,先写出题目所要求的遍历方式下的结点访问序列,根据此序列找出题目要求中结点的前驱和后继,然后连接线索。图4—7中二叉树的中序遍历序列为D,B,E,A,C。结点E的前驱为B,后继为A,因此其右线索应该指向A,结果如图4—8所示。
总结:
(1)引入二叉线索树的目的:加快查找结点的前驱或后继的速度。
(2)二叉树在线索化后,仍不能解决的问题:后序线索二叉树中求后序后继。
(3)n个结点的线索二叉树上含有的线索树为:n+1。
转载请注明原文地址:https://kaotiyun.com/show/xz3i777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列选项中,不属于西汉农业发展状况的是()
如下图所示为一个网络连接的示意图,主机1到主机2采用了SLIP网络连接,SLIP网络可以传输的最大数据段是296字节,主机2和主机3使用了以太网连接。请问:(1)为了使IP不分片,主机1可以在TCP包中承载多少数据?(2)主机3可以在TCP包中承载多
Demandpaging算法是paging算法在虚拟存储空间管理的扩展。其主要的改进是:仅当需要访问某页面时,如果它不在内存,把它调入内存。按照这个思路,将segmentation算法(段式存储管理算法)扩展到虚拟存储空间管理,也可以产生类似的算法,不妨
试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的:ProcessPO:do{flag[0]=true;While(flag[1]);
某机字长32位,它的存储容量为256MB,按字节编址,则它的寻址范围大小为()。
若二叉树的前序序列为DABCEFG,中序序列为BACDFGE,则其层次序列为()。
操作系统采用页式存储管理方法,要求()。
给定序列{3,5,7,9,11,13,15,17),(1)按表中元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成后的二叉排序树,并求在等概率情况下查找成功的平均查找长度。(2)按表中元素的顺序构造一棵平衡二叉树,并求其在等概率情
在AOE网络中关键路径叙述正确的是()。
设置当前工作目录的主要目的是____。
随机试题
意识流小说
患者,男,52岁,高血压心脏病病史10年,1天前因上呼吸道感染在门诊静脉滴注抗生素速度较快,2小时前出现呼吸困难。该患者发现呼吸困难最可能是由于()
胃大部切除术后贫血的主要原因是
男,40岁。突发右腰部剧痛3小时,疼痛向右下腹放射,伴恶心,呕吐。最可能的疾病是
欲用95%乙醇和蒸馏水配制70%乙醇1000ml,所取95%乙醇体积约为()。
简述当代中小学生发展的时代特点。
绿色GDP占GDP的比重越高表明国民经济增长的正面效应越高,负面效应越低。反之亦然。()
Thebiographerhastodancebetweentwoshakypositionswithrespecttothesubject(研究对象).Toclosearelation,andthewriterm
Whatdoweknowabouttheweather?
股指期货近期与远期交割月份合约间的理论价差与()等有关。
最新回复
(
0
)