首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设k是中序线索二叉树中一个有左子女的结点,且k不是根结点,则k在中序序列下的直接前驱结点是( )。
设k是中序线索二叉树中一个有左子女的结点,且k不是根结点,则k在中序序列下的直接前驱结点是( )。
admin
2019-12-10
42
问题
设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://jikaoti.com/ti/aeDjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列选项中,不属于西汉农业发展状况的是()
某32位机(机器字长32位)的一台外设通过32位总线与系统内存相连。CPU每秒执行100条指令,平均每条指令需要5个机器周期,其中3个周期必须访问内存,内存读写需一个机器周期,假定CPU在95%的时间内持续执行“背景程序”,且这段时间内不执行I/O指令。现
某系统中n个相互独立的生产者进程为一个消费者进程提供数据,假设每个生产者提供的数据写入各不相同的缓冲区,且生产者写缓冲区的速度比消费者读缓冲区的速度快,则缓冲区个数的最优值应为()。
桌上有一空盘,只允许放入一个水果。爸爸专向盘中放苹果,妈妈专向盘中放橘子,女儿专等着吃盘中的苹果,儿子专等着吃盘中的橘子。试用P,V原语实现爸爸、妈妈、儿子和女儿间能同步的程序。
设某计算机系统有一块CPU、一台输入设备、一台打印机。现有两个进程同时进入就绪状态,且进程A先得到CPU运行,进程B后运行。进程A的运行轨迹为:计算50ms,打印信息100ms,再计算50ms,打印信息100ms,结束。进程B的运行轨迹为:计算50
序列的“中值记录”指的是:如果将此序列排序后,它是第n/2个记录。试写出一个求中值记录的算法。
在操作系统的以下功能中,不需要硬件支持的是()。
在实现文件系统时,一般为加快文件目录的检索速度,可利用“文件控制块部分装入”的方法。假设目录文件(即文件控制块)存放在磁盘上,磁盘的每个盘块为512B,每个目录项占128B,其中文件名占11B。为提高检索速度,通常将目录项分解成两部分,第一部分(包括文件名
某机字长32位,采用定长操作码,单字长指令,共有机器指令100条,CPU内部有通用寄存器32个,可作变址寄存器用,存储器按字节编址,指令拟用直接寻址、间接寻址、变址寻址和相对寻址等4种寻址方式。写出4种寻址方式下,有效地址EA的表达式。
假设一个主频为1GHz、CPI为5的CPU需要从某个成块传送的I/O设备读取1000B的数据到主存缓冲区中,该I/O设备一旦启动即按50KB/s的数据传输率向主机传送1000B数据,每个字节的读取、处理并存入内存缓冲区需要1000个时钟周期,则以下4种
随机试题
A.处方B.麻醉药品和第一类精神药品处方C.医疗用毒性药品、第二类精神药品处方D.普通处方、急诊处方、儿科处方E.中药饮片处方()保存期限为3年
钢筋焊接前必须根据施工条件进行试焊,按不同的焊接方法至少抽取每组()个试样进行基本力学性能检验,合格后方可正式施焊。
衡量政府偿还债务能力的指标包括()。
背景:某汽车模具厂厂房工程,建筑面积6000m2,地上2层,首层层高13m,二层层高3.6m。独立柱基础,现浇混凝土框架结构,首层结构柱一次浇筑。工期200日历天,由于工期紧张,现场需要多点交叉施工。施工过程中发生了如下事件:事件一:首层施工前,项目部
借款人信用承受能力的主要内容不包括()。
风险资本计量不包括()的计量。
下列关于效果主导型绩效考评的叙述,正确的有()。
引起音质不同的三要素是:发音体、_____________和_____________。
表达式4+5\6*7/8Mod9的值是()。
Readthearticlebelow.Choosethebestsentencefromthelistonthenextpagetofilleachofthegaps.Foreachgap(1
最新回复
(
0
)