2021计算机考研:如何在线索树中找结点的后继?

最后更新时间:2020-08-28 16:14:43
辅导课程:魔鬼集训 在线咨询
想找考研难度低但就业行情看好的院校专业?来跨考考研全年魔鬼集训二期,帮你找专业,强复习 了解一下>>

  对于打算报考2021考研计算机的考生们来说复习是难点,很多本专业或者跨专业的学生在备考考研数据结构中经常遇到一个难点问题,如何在线索树中找结点的后继?虽然有些题目设置的灵活多变,有的时候甚至可能分析不出来题目的考点在这里。下面小编整理了详细内容,供大家参考。

  如何在线索树中找结点的后继?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  最后希望各位小伙伴们在考研的路上不断迈进,继续加油,我们下次再见。

  (注:本文来自网络,如有侵权,请联系删除)

  2022考研征程已开启,了解竞争压力,盘点历年考研人数,请前往→近10年考研人数汇总;院校难抉择,跨考复习入门难,自制力不足复习无章法,跨考考研全年集训营专为你而来!

  对于2021考生,成绩出来后,复试调剂迫在眉睫,想要在复试和调剂间找到自己的位置,断进入复试概率,前往点击评估复试入选率 手机打开效果更佳哦);
        若此战失利,与理想院校失之交臂,没关系!天没塌!二战集训营,我们等你,挽救2021的失误,这次,我们和你一起再战考研!

点击右侧咨询或直接前往了解更多

2022考研全年集训
2022考研形式分析 各专业院校排名情况 从历年会计专硕报录比说MPAcc考研难吗
2022考研时间及注意事项 全年复习方案制定
从金融专硕报录比解读金专考研哪些院校最好考 考研难度分析及自身情况解读
2021考研复试调剂 2021考研复试·了解导师 通知!2021考研第一批调剂信息来了!
历年考研复试面试常见话题汇总 全国各省研招办官网网址及微信公众号汇总!
复试时要查本科成绩单怎么办? 2021考研复试参考书目

跨考考研课程

班型 定向班型 开班时间 全科协议班 全科标准班 课程介绍 咨询
全年集训二期 定向-政英统考班 4.20-12.20 80800起 60800 公共课集训面授课程+专业课集训面授课程+专业课针对性一对一课程+高清公共课线上精英补课课程+KTS专业课课程+班主任全程督学服务+全程规划体系+全程测试体系+全程精细化答疑+择校择专业能力定位体系+全年关键环节指导体系+初试保过加强课+初试协议班专属服务+复试全科协议班服务
2021无忧畅学 定向-数政英+(经济学;金融专硕;国际商务硕士;计算机;通信;电气;机械) 每月20日 26800起 16800起 基础阶在线课程+强化阶在线课程+真题阶在线课程+冲刺阶在线课程+专业课针对性一对一课程+班主任全程督学服务+全程规划体系+全程测试体系+全程精细化答疑+择校择专业能力定位体系+全年关键环节指导体系+初试保过加强课+初试协议班专属服务+复试全科标准班服务

①凡本网注明“稿件来源:跨考网”的所有文字、图片和音视频稿件,版权均属北京尚学硕博教育咨询有限公司(含本网和跨考网)所有,任何媒体、网站或个人未经本网协议授权不得转载、链接、转帖或以其他任何方式复制、发表。已经本网协议授权的媒体、网站,在下载使用时必须注明“稿件来源,跨考网”,违者本网将依法追究法律责任。

②本网未注明“稿件来源:跨考网”的文/图等稿件均为转载稿,本网转载仅基于传递更多信息之目的,并不意味着再通转载稿的观点或证实其内容的真实性。如其他媒体、网站或个人从本网下载使用,必须保留本网注明的“稿件来源”,并自负版权等法律责任。如擅自篡改为“稿件来源:跨考网”,本网将依法追究法律责任。

③如本网转载稿涉及版权等问题,请作者见稿后在两周内速来电与跨考网联系,电话:400-883-2220