首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下列各种线索二叉树中,采用二叉链表存储,遍历时仍需要栈的支持的是(9)。
下列各种线索二叉树中,采用二叉链表存储,遍历时仍需要栈的支持的是(9)。
admin
2010-01-23
35
问题
下列各种线索二叉树中,采用二叉链表存储,遍历时仍需要栈的支持的是(9)。
选项
A、前序线索二叉树
B、中序线索二叉树
C、后序线索二叉树
D、前、后、中序线索二叉树
答案
C
解析
易知,前、中、后序遍历二叉树的递归或者非递归算法都用到栈。遍历线索二叉树实际上就是找结点的后继。前序线索二叉树中,除前序遍历最后一个元素无后继外。任一结点的后继便为左孩子(若左子树非空)或者右孩子(若左子树为空)或者是其右线索(若该结点是叶子结点),只要顺着指针便可以方便地找到后继,显然不需要用到栈。中序线索二叉树中,除中序遍历最后一个元素无后继外,寻找任一结点的后继的过程如下:若该结点有右线索,则该右线索指示的便是后继;否则,该结点右子树最左下的结点便是后继。可以顺着该结点指向右子树的指针向下找到这个最左下的结点,不需要用栈。因此,遍历中序线索二叉树也不需要栈的支持。在后序线索二叉树中求后继要分三种情况来讨论:①若结点W是根结点,则W的后继为空;②若结点W是其双亲结点的右孩子,或者W是其双亲结点的左孩子且W的双亲没有右子树,则W的后继为其双亲结点;③若结点W是其双亲结点的左孩子且其双亲结点有右子树,则W的后继为其双亲结点右子树上按后序遍历的第一个结点。可见,在后序线索化树(以二叉链表存储)上找后继时需要知道结点双亲,这就需要栈的支持。如 13-28所示,从后序遍历第一个结点E开始,顺着E的右线索可以找到E的后继D,当要找D的后继就麻烦了,因为这个时候D的两个指针都指向E,而B只有单向指向D的指针 (不管用),因此要找到D的后继B就需要栈的支持。
转载请注明原文地址:https://jikaoti.com/ti/a3a7FFFM
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
The purpose of the requirements definition phase is to produce a clear, complete, consistent, and testable(6)of the technical re
在缺省配置的情况下,交换机的所有端(49)。连接在不同交换机上的,属于同一VLAN的数据帧必须通过(50)传输。
下面有关NTFS文件系统优点的描述中,(5)是不正确的。要把FAT32分区转换为NTFS分区,并且保留原分区中的所有文件,不可行的方法是(6)。
在UNIX操作系统中,若用户键入的命令参数的个数为1时,执行cat$1命令;若用户键入的命令参数的个数为2时,执行cat>>$2<$1命令。请将下面所示的Shell程序的空缺部分补齐。case(51)in1)cat$1;;2)cat
四台Linux主机通过图1所示的方式互联起来,则实现PCI与PC4之间互访的步骤为:1.运行(46命令关闭计算机,在PC2与PC3上添加第二块网卡(ethl),重新启动;2.在PC2与PC3上为第二块网卡分配IP地址,并激活该网络接口,对
PPP使用(38)协议。相对于OSI模型,它提供(39)服务。对于PPP,远程服务器可以为本地客户提供一个(40)IP地址。
以下Windows命令中,可以用于验证端系统地址的是(52);可以用于识别分组传送路径的是(53);如果要终止一个ping会话,正确的操作是(54)。以下应用中,对网络带宽性能影响最大的应用上(55)。OSPF和RIP都是Internet中的路由协议,与R
在RAS上存在的两个RJ45的端口(“console”与“AUX”)的作用分别是什么?在调用超级终端程序进行设备连接时,给出正确的设备连接参数,参数主要包括串口数据传输率,数据位数,停止位数以及是否有奇偶校验。
IPv6地址的格式前缀用于表示地址类型或子网地址,例如60位的地址前缀12AB00000000CD3有多种合法的表示形式,下面的选项中,不合法的是(56)。
Data mining is an(66)research field in database and artificial intelligence. In this paper, the data mining techniques are intro
随机试题
IPv6地址包括________、组播地址和任播地址。
自动曝光控制系统,探测器的种类有
甲个人缴纳的医疗保险费一般为本人工资收人的( )。甲的失业保险金的标准应( )。
关于法律原则的适用,下列哪些选项是错误的?(2008年试卷一第51题)
五个瓶子都贴了标签,其中恰好贴错了三个,贴错的可能情况共有多少种?()
简述中世纪教育的特点及其历史地位。
数据流图的类型有【】和事务型。
用黑盒技术测试用例的方法之一为()。
In______marketforskilledlabor,corporationsareincreasinglybuyinghomesforhotnewhires,a______oncereservedfortopexe
Thedeadlybirdflusofarhasclaimedaconfirmed18livesinVietnamandThailand,thoughthesuspectedtollishigherat23.
最新回复
(
0
)