十八年专注考研辅导
因为专注,所以出色

0371-60904200 全国咨询热线服务
您所在的位置: 首页 > 考研备考 > 知识总结 > 正文
知识总结

2023考研计算机专业课考点复习:如何在线索树中找结点的后继

来源:天任考研  |  更新时间:2022-12-24 10:09:10  |  关键词:

  •  
  •  
  •  

2023考研计算机专业课考点复习:如何在线索树中找结点的后继

  2023考研科目中,很多考生将大量时间放在了数英政上,在这里小编提醒各位考研人别忽视专业学科的学习。下面天任小编为大家整理了“2023考研计算机专业课考点复习:如何在线索树中找结点的后继”,希望能帮助大家更好的准备专业科目。


  2023考研计算机专业课考点复习:如何在线索树中找结点的后继

  (1)中序线索树中找结点的后继

  ①树中所有叶子结点的右链是线索,则右链域直接指示了结点的后继。

  ②树中所有非终端结点的右链均为指针,根据中序遍历的规律,结点的后继应是遍历其右子树时访问的第一个结点,即右子树中最左下的结点。

  反之,在中序线索树中找结点前驱的规律是:若其左标志为“1”,则左链为线索,指示其前驱,否则遍历左子树时最后访问的一个结点(左子树中最右下的结点)为其前驱。

  (2)后序线索树中找结点后继

  ①若结点x是二叉树的根,则其后继为空

  ②若结点x是其双亲的右孩子或是其双亲的左孩子且其双亲没有右子树,则其后继即为双亲结点

  ③若结点x是其双亲的左孩子,且其双亲有右子树,则其后继为双亲的右子树上按后序遍历列出的第一个结点。

  可见,在后序线索化树上找后继时需知道结点双亲,即需带标志域的三叉链表作存储结构。

  最后给大家留一个题目,希望可以帮助各位小伙伴们检验一下知识点的掌握情况。

  二叉树在线索化后,仍不能有效求解的问题是( )。

  A.先序线索二叉树中求先序后继

  B.中序线索二叉树中求中序后继

  C.中序线索二叉树中求中序前驱

  D.后序线索二又树中求后序后继

  小伙伴们,看到这里的时候相信大家已经有了自己的答案,在这里我们对一下正确选项:D。简单分析一下:不是每个结点经过线索都可以直接找到它的前驱和后继。在先序线索二叉树中查找一个结点的先序后继很简单,而查找先序前驱必须知道该结点的双亲结点。中序线索二叉树中根据中序遍历的规律查找中序前驱和中序后继也是很方便的。同样,在后序线索二叉树中查找一个结点的后序前驱也很简单,而查找后序后继也必须知道该结点的双亲结点,而二叉链表中没有存放双亲的指针。

  以上是天任考研小编为大家整理的“2023考研计算机专业课考点复习:如何在线索树中找结点的后继”的相关内容,希望为大家准备专业科目方面上提供一些参考和帮助。成功不是一簇而就的,大家一定要在学习上用对方法,坚持就能看到进步。

免责声明:本站所提供的内容均来源于网友提供或网络搜集,由本站编辑整理,仅供个人研究、交流学习使用,不涉及商业盈利目的。如涉及版权问题,请联系本站管理员予以更改或删除。邮箱:zzqihangpx@163.com 电话:0371-60903400

天任考研微信群

扫码加入2026考研群
获取考研咨询一对一服务


热报课程

报考信息


备考指南


报名咨询电话:0371-60904200
Copyright©2006-2020  郑州市天任教育科技有限公司 豫ICP备2024092498号

免责声明:本站所提供的内容均来源于网友提供或网络搜集,由本站编辑整理,仅供个人研究、交流学习使用,不涉及商业盈利目的。如涉及版权问题,请联系本站管理员予以更改或删除。电话:0371-60904200