下列各种线索二叉树中，采用二叉链表存储，遍历时仍需要栈的支持的是(9)。

admin2010-01-23 39

问题下列各种线索二叉树中，采用二叉链表存储，遍历时仍需要栈的支持的是(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)

下列各种线索二叉树中，采用二叉链表存储，遍历时仍需要栈的支持的是(9)。

软件设计师上午基础知识考试

软考中级

Socket的通信方式包括(62)，(63)是最常用的套接字类型。

DES加密算法中，函数f的输出是(51)位。DES算法是分组密码，数据分组长度是(52)位。用软件方法实现DES一般至少比RSA快100倍。DES通过(53)方法产生密文。

避免死锁的一个著名的算法是(26)。

公钥密码是(39)。常用的公钥加密算法有(40)，它可以实现加密和数字签名，它的一个比较知名的应用是(41)，这种应用的协商层用公钥方式进行身份认证，记录层涉及到对应用程序提供的信息的分段、压缩、数据认证和加密。

国际标准化组织制定的OSI网络体系管理协议是(58)，另外，ISO还定义了5个管理功能域，(59)属于性能管理域。IAB制定的网络管理协议是SNMP，在SNMP管理框架中使用的管理信息库为(60)。管理站(Manager)通过GetRequest命令查询代

在Linux系统中，采用()一命令查看进程输出的信息，得到下图所示的结果。系统启动时最先运行的进程是()，下列关于进程xinetd的说法中正确的是()。

测试是保证软件质量的重要手段。根据国家标准GB8566—88《计算机软件开发规范扩的规定，应该在(10)阶段制定系统测试计划。

为进行内生肌酐清除率检查，应嘱病人检查前连续3天禁食

上消化道大出血伴休克的首要护理措施是

假设有两家厂商，它们面临的是线性需求曲线P=A-BY，每家厂商边际成本为0，古诺均衡情况下的产量是()。

与逐步结转分步法相比，平行结转分步法的缺点有()。

视频题：视频内容描述：四组画面，同时播放。第一个画面是有人晕倒，第二个画面是有小孩走失，第三个画面中有人在打架，第四个画面中是一起盗窃事件。问题：请描述你在这些画面中所看到的情况。

已知0是A＝的特征值，求a和A的其他特征值及线性无关的特征向量．

Accordingtothetext,"amassexodus"(Para.6)mostprobablymeansWhichofthefollowingcannotdescribethepublic’sopinio

将文件夹下JIN文件夹中的SUN.C文件复制到文件夹下的MQPA文件夹中。