首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和c函数代码,将应填入 (n) 处的字句写在答题纸的对应栏内。 【说明】 对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点,且每个结点仅访问一次的过程。函数InOrder。()借助栈实现二叉树的非递归中序遍历运算
阅读下列说明和c函数代码,将应填入 (n) 处的字句写在答题纸的对应栏内。 【说明】 对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点,且每个结点仅访问一次的过程。函数InOrder。()借助栈实现二叉树的非递归中序遍历运算
admin
2010-04-08
42
问题
阅读下列说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
假设某公司营销系统有营销点关系S(营销点,负责人姓名,联系方式)、商品关系P(商品名,条形码,型号,产地,数量,价格),其中,营销点唯一标识S中的每一个元组。每个营销点可以销售多种商品,每一种商品可以由不同的营销点销售。关系S和P的主键分别为(15),S
为了解系统在何种服务级别下会崩溃,应进行___________。
在以阶段划分的编译器中,符号表管理和()贯穿于编译器工作始终。
传统编译器进行词法分析、语法分析、代码生成等步骤的处理时,前一阶段处理的输出是后一阶段处理的输入,则采用的软件体系结构风格是①。该体系结构的优点不包括②。①处应填入?
对于逻辑表达式(((a>0)&&(b>0))‖c<5),需要______个测试用例才能完成条件组合覆盖。
某系统中有一个中央数据存储,模块A负责接收新来的数据并修改中央数据存储中的数据,模块B负责访问中央数据存储中的数据,则这两个模块之间的耦合类型为________________。若将这两个模块及中央数据合并成一个模块,则该模块的内聚类型为_________
为检测系统所能承受的数据容量,应进行()。
某软件公司在招聘软件评测师时,应聘者甲向公司做如下保证:①经过自己测试的软件今后不会再出现问题;②在工作中对所有程序员一视同仁,不会因为在某个程序员编写的程序中发现的问题多,就重点审查该程序,以免不利于团结;③承诺不需要其他人员,自己就可以独立进行测
下图是①设计模式的类图,该设计模式的目的是②,图中,Abstraction和RefinedAbstraction之间是③关系,Abstraction和Implementor之间是④关系。④处应填入?
随机试题
投资者完全绕过证券商,相互间直接进行证券交易而形成的市场,称为()。
冷却系统有什么作用?
下列关于脾梗死,错误的是
不影响自动冲洗照片干燥不良的因素是
林女士,持续性高热,体温40.2℃,遵医嘱给予冰帽降温,下列措施不妥的是
患者,男,55岁。症见胸闷、心前区刺痛。治疗宜选用复方丹参片。复方丹参片除可活血化瘀外,还可
药品上市前临床研究存在的局限性包括
普通水泥的主要特性有()。
2009年10月1日上午,在北京天安门广场举行了首都各界庆祝中华人民共和国成立60周年大会,中共中央总书记、国家主席、中央军委主席胡锦涛发表重要讲话,之后举行盛大的阅兵式和群众游行。10月1日晚,在北京天安门广场举行了以()为主题的联欢晚会。
春秋时期,鲁国实行初税亩的目的是()。
最新回复
(
0
)