首页 25考研 在职考研 0元畅学 26考研

新东方在线 > 考研 > 计算机 > 考研计算机复习指导 > 正文

扫码加入训练营

牢记核心词

学习得礼盒

2020考研计算机备考：如何在线索树中找结点的后继?

2019-07-11 17:34:00来源：网络

　　2020年计算机考研复习已经开始，新东方在线在此整理了2020考研计算机备考：如何在线索树中找结点的后继?，希望能帮助大家!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　在这里我们对一下正确选项：D。简单分析一下：不是每个结点通过线索都可以直接找到它的前驱和后继。在先序线索二叉树中查找一个结点的先序后继很简单，而查找先序前驱必须知道该结点的双亲结点。中序线索二叉树中根据中序遍历的规律查找中序前驱和中序后继也是很方便的。同样，在后序线索二叉树中查找一个结点的后序前驱也很简单，而查找后序后继也必须知道该结点的双亲结点，而二叉链表中没有存放双亲的指针。


本文关键字: 2020考研计算机

考研英语核心词汇营

背词+听课+练习+督学，学习得礼盒

更多资料

添加班主任领资料

添加考研班主任
免费领取考研历年真题等复习干货资料

  • 1.打开手机微信【扫一扫】，识别上方二维码；
  • 2.添加班主任，可领取学习资料。
更多>>
更多内容
25考研 在职研 AI择校 去测评 领资料

关注新东方在线考研服务号

获得21考研真题及答案解析

1. 打开手机微信【扫一扫】，识别上方二维码；
2.点击【关注公众号】，获取资料大礼包。

考研资料大礼包

历年考研真题及答案解析下载

英语一 英语二 政治 数学一 数学二 数学三 西医综合 教育综合 心理学综合
立即下载
近10年考研真题及答案免费下载
更多>>
更多公开课>>
更多>>
更多资料
我要
反馈 返回
首页
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

京ICP证050421号 京ICP备05067669号-2 京公网安备11010802017616号 网络视听许可证0110531号 京网文(2016)1303-163号

Copyright © 2011-2018 新东方教育科技集团有限公司, All Rights Reserved

违法和不良信息举报电话: 010-81401500 举报邮箱: sec@xdfzx.com 网上有害信息举报专区