首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设k是中序线索二叉树中一个有左子女的结点,且k不是根结点,则k在中序序列下的直接前驱结点是( )。
设k是中序线索二叉树中一个有左子女的结点,且k不是根结点,则k在中序序列下的直接前驱结点是( )。
admin
2019-12-10
51
问题
设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
学硕统考专业
相关试题推荐
民族区域自治制度
在一个长度为n(n>1)的带头结点的单链表h上,设有尾指针r(指向尾结点),则执行()操作与链表的长度有关。
一个使用选择性重传协议的数据链路层协议,如果采用了5位的帧序列号,那么可以选用的最大窗口是()。
若有4个进程共享同一程序段,每次允许3个进程进入该程序段,用P、V操作作为同步机制,则信号量S的取值范围是()。
荷兰国旗问题:设有一个仅红、白、蓝三种颜色的条块组成的条块序列,请编写一个时间复杂度为O(n)的算法,使得这些条块按红、白、蓝的顺序排好,即排成荷兰国旗图案。
某公司的局域网设置如下所示,两个局域网通过路由器连接到NAT、服务器上,并且通过NAT服务器连接到Internet上。局域网1的掩码是192.168.14.0/25,局域网2的掩码是192.168.14.128/25,NAT服务器的内部IP地址为192.1
IEEE754标准规定的64位浮点数格式中,符号位为1位,阶码为11位,尾数为52位。则它所能表示的最小规格化负数为()。
若线性表最常用的运算是查找第i个元素及其前驱的值,则采用()存储方式节省时间。
下图所示为双总线结构机器的数据通路,IR为指令寄存器,PC为程序计数器(具有自增功能),M为主存(受R/W信号控制),AR为地址寄存器,DR为数据缓冲寄存器,ALU由加、减控制信号决定完成何种操作,控制信号G控制的是一个门电路。另外,线上标注有小圈表示有控
在某一个单处理机的系统中,外接了一台打印机,一台输入设备。当前在系统中有二个进程P0、P1已经就绪,进程P0首先获得处理机运行,调度算法为先来先服务,进程P0、P1的运行要求是这样的:P0:计算100ms,打印信息200ms,继续计算100ms,打印信息
随机试题
下列画线字释义全部正确的一组是()
在Windows资源管理器窗口中,左窗口显示的内容是()
心肌缺血很少影响到
给予地高辛每日维持量治疗,地高辛的半衰期为
A、水、钠潴留B、促进胃酸分泌C、抑制免疫功能D、抑制蛋白质合成E、兴奋中枢神经系统糖皮质激素禁用于胃溃疡是因为
甲诉乙侵权纠纷一案,法院适用普通程序对案件进行审理,在答辩期满之前双方当事人同意进行调解。则关于本案的调解,下列说法中正确的是:()
某建设单位和施工单位签订了某市政公用工程施工合同,合同中约定:建筑材料由建设单位提供:由于非施工单位原因造成的停工,机械补偿费为200元/台班,人工补偿费为50元/日工;总工期为120d;竣工时间提前奖励为3000元/d,误期损失赔偿费为5000元/d。经
世界语在未来有可能替代自然语言作为人们的母语或第一语言。()
各国在出生国籍上通常采用的原则有()。
以太网交换机的交换方式有3种,这3种交换方式不包括__________。(2011年上半年试题)
最新回复
(
0
)