首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和c函数代码,将应填入 (n) 处的字句写在答题纸的对应栏内。 【说明】 对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点,且每个结点仅访问一次的过程。函数InOrder。()借助栈实现二叉树的非递归中序遍历运算
阅读下列说明和c函数代码,将应填入 (n) 处的字句写在答题纸的对应栏内。 【说明】 对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点,且每个结点仅访问一次的过程。函数InOrder。()借助栈实现二叉树的非递归中序遍历运算
admin
2010-04-08
27
问题
阅读下列说明和c函数代码,将应填入 (n) 处的字句写在答题纸的对应栏内。
【说明】
对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点,且每个结点仅访问一次的过程。函数InOrder。()借助栈实现二叉树的非递归中序遍历运算。
设二叉树采用二叉链表存储,结点类型定义如下:
typedef struct BtNode{
ElemTypedata; /*结点的数据域,ElemType的具体定义省略*/
struct BtNode*ichiid,*rchild; /*结点的左、右弦子指针域*/
)BtNode,*BTree;
在函数InOrder()中,用栈暂存二叉树中各个结点的指针,并将栈表示为不含头结点
的单向链表(简称链栈),其结点类型定义如下:
typedef struct StNode{ /*链栈的结点类型*/
BTree elem; /*栈中的元素是指向二叉链表结点的指针*/
struct StNode*link;
}S%Node;
假设从栈顶到栈底的元素为e
n
、e
n-1
、…、e
1
,则不含头结点的链栈示意图如图5—5
所示。
【C函数】
int InOrder(BTree root) /*实现二叉树的非递归中序遍历*/
{
BTree ptr; /*ptr用于指向二又树中的结点*/
StNode*q; /*q暂存链栈中新创建或待删除的结点指针+/
StNode*stacktop=NULL; /*初始化空栈的栈顶指针stacktop*/
ptr=root; /*ptr指向二叉树的根结点*/
while( (1 ) I I stacktop!=NULL){
while(ptr!=NULL){
q=(StNode*)malloc(sizeof(StNode));
if(q==NULL)
return-1;
q->elem=ptr;(2) ;
stacktop=q; /*stacktop指向新的栈顶*/
ptr=(3 ) ; /*进入左子树*/
}
q=stacktop; (4) ; /*栈顶元素出栈*/
visit(q); /*visit是访问结点的函数,其具体定义省略*/
ptr= (5) ; /*进入右子树*/
free(q); /*释放原栈顶元素的结点空间*/
}
return 0;
}/*InOrder*/
选项
答案
(1)ptr! =NULL或ptr! =0或ptr(2)q->link=stacktop(3)ptr->lchild(4)stacktop=stacktop->link或stacktop=q->link(5)q->elem->rchild
解析
对非空二叉树进行中序遍历的方法是:先中序遍历根节点的左子树,然后访问根节点,最后中序遍历根节点的右子树。从以上算法的执行过程可知,从树根出发进行遍历时,递归调用InOrderTraversing(root-LeftChild)使得遍历过程沿着左孩子分支一直走向下层节点,直到到达二叉树中最左下方的节点(设为f)的空左子树为止,然后返回节点,再由递归调用InOrder Traversing(root->RightChild)进入f的右子树,并重复以上过程。在递归算法执行过程中,辅助实现递归调用和返回处理的控制栈实际上起着保存从根节点到当前节点的路径信息。用非递归算法实现二叉树的中序遍历时,可以由一个循环语句实现从指定的根节点m发,沿着左孩子分支一直到头(到达一个没有左子树的节点)的处理,从根节点到当前节点的路径信息(节点序列)可以明确构造一个栈来保存。
转载请注明原文地址:https://kaotiyun.com/show/WSDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
将高级语言程序翻译为机器语言程序的过程中,常引入中间代码,其好处是()。
在以阶段划分的编译器中,符号表管理和()贯穿于编译器工作始终。
修改现有软件系统的设计文档和代码以增强可读性,这种行为属于________维护。
某指令流水线由5段组成,各段所需要的时间如下图所示。连续输入10条指令时的吞吐率为(6)。
对某商店业务处理系统采用数据流图(DFD)进行功能建模,其中“检查订货单”是其中的一个①。由于在进行订货单检查时,需要根据客户的欠款情况、订单金额等多个条件判断是否采取发出催款单、准备货物、发出发货单等行为,此时适合采用②进行描述。①处
标准符合性测试中的标准分类包括______。①数据内容类标准②通信协议类标准③开发接口类标准④信息编码类标准
Bug记录信息包括________________。①被测软件名称②被测软件版本③测试人④错误等级⑤开发人⑥详细步骤
以下关于设计功能测试用例的叙述,______是不正确的。A.尽量用80%测试用例覆盖20%的核心业务模块B.功能测试用例中不包括功能的依从性测试用例C.功能测试用例中包括业务流,也包括测试数据D.功能测试用例的设计应注意缺陷群集现象
下面为C语言程序,边界值问题可以定位在(45)。 int data(3), int i, for(i=1, i<=3, i++)data(i)=100
序言性注释是指在每个程序或模块开头的一段说明,起辅助理解程序的作用,一般包括:程序的表示、名称和版本号;程序功能描述;接口与界面描述;输入输出数据说明:开发历史;与运行环境有关的信息等。下列叙述中不属于序言性注释的是(23)。
随机试题
[2015]ABC会计师事务所的A注册会计师担任多家被审计单位2014年度财务报表审计的项目合伙人,遇到下列导致出具非标准审计报告的事项:(3)因丙公司严重亏损,董事会拟于2015年对其进行清算,管理层运用持续经营假设编制了2014年度财务报表,
在对公允价值变动净损益进行分析时,关键要注意()
我国《清洁生产促进法》规定的清洁生产措施包括()
在下列内容中,属于被动控制措施的是( )。
地下防水混凝土施工中,施工缝的留设及施工的说法正确的有()。
会计人员对省会计学会职业道德委员会的处理存有异议者,可以()。
从所给的四个选项中,选择最合适的一个填人问号处,使之呈现一定的规律性()。
下列说法错误的是()。
In1993,NewYorkStateorderedstorestochargeadepositonbeverage(饮料)containers.Withinayear,consumershadreturnedmi
中国将坚定不移地奉行独立自主的和平外交政策,继续加强同发展中国家的团结合作,同它们一道维护发展中国家正当合理的权益。同时,我们要进一步致力于稳定周边、巩固睦邻友好。我们还将不断地充实与各个大国已经建立或正在建立的未来关系框架的内涵。我们将更积极地参与国际事
最新回复
(
0
)