2. 考研
  3. 设k是中序线索二叉树中一个有左子女的结点，且k不是根结点，则k在中序序列下的直接前驱结点是( )。

设k是中序线索二叉树中一个有左子女的结点，且k不是根结点，则k在中序序列下的直接前驱结点是( )。

admin2019-12-10  85
问题 设k是中序线索二叉树中一个有左子女的结点，且k不是根结点，则k在中序序列下的直接前驱结点是(    )。
选项 A、k的左线索(指示中序前驱)所指示的结点
B、从k父结点的左子女开始沿右子女链走到底的结点
C、从k的左子女开始沿右子女链走到底的结点
D、从k的左子女开始沿左子女链走到底的结点
答案C
解析 如果k没有左子女，则k的左指针即为指向k的中序前驱的线索；当k有左子女时，k的中序直接前驱结点是k的左子树中中序的最后一个结点，即从k的左子女开始沿右链走到右指针不再是右子女的结点为止，该结点即为k的中序前驱结点。
    说明：上述二叉树的线索化算法其实考试中涉及的不多，本节在考试中涉及最多的是，在选择题中给你一棵二叉树，让你指出其中一个结点的线索按照某种线索化方法所应该指向的结点。
    例如：请画出图4—6中按照中序线索化方法线索化后E结点的右线索的接连情况。
    解决这类题的方法为，先写出题目所要求的遍历方式下的结点访问序列，根据此序列找出题目要求中结点的前驱和后继，然后连接线索。图4—6中二叉树的中序遍历序列为D，B，E，A，C。结点E的前驱为B，后继为A，因此其右线索应该指向A，结果如图4—7所示。

总结：(1)引入二叉线索树的目的：加快查找结点的前驱或后继的速度。(2)二叉树在线索化后，仍不能解决的问题：后序线索二叉树中求后序后继。(3)n个结点的线索二叉树上含有的线索树为n+1。
转载请注明原文地址:https://kaotiyun.com/show/j63i777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)