首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和c函数代码,将应填入 (n) 处的字句写在答题纸的对应栏内。 【说明】 对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点,且每个结点仅访问一次的过程。函数InOrder。()借助栈实现二叉树的非递归中序遍历运算
阅读下列说明和c函数代码,将应填入 (n) 处的字句写在答题纸的对应栏内。 【说明】 对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点,且每个结点仅访问一次的过程。函数InOrder。()借助栈实现二叉树的非递归中序遍历运算
admin
2010-04-08
70
问题
阅读下列说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
在数据库逻辑结构设计阶段,需要(20)阶段形成的(21)作为设计依据。(20)
程序中常采用变量表示数据,变量具有名、地址、值、作用域、生存期等属性。关于变量的叙述,(19)是错误的。
______不属于易用性测试范畴。A.软件产品使用户能理解软件是否合适以及如何能将软件用于特定的任务和使用条件的能力B.软件产品使用户能操作和控制它的能力C.对软件中的缺陷或失效原因进行诊断,或识别待修改部分的能力D.软件产品吸引用户的能力
当用户需求不清晰、需求经常发生变化、系统规模不太大时,最适宜采用的软件开发方法是__________。
某开发小组的任务是开发一个大型软件产品的图形用户界面,宜采用()开发过程模犁。
银行系统数据流图中,某个加工根据客户的多个不同属性的值来执行不同的操作,则对该加工最适宜采用()描述。
某企业职工关系EMP(E_no,E_name,DEPT,E_addr,E_tel)中的属性分别表示职工号、姓名、部门、地址和电话;经费关系FUNDS(E_no,E_limit,E_used)中的属性分别表示职工号、总经费金额和已花费金额。若要查询部门为“开
给定包含n个正整数的数组A和正整数x,要判断数组A中是否存在两个元素之和等于x。先用插入排序算法对数组A进行排序,再用以下过程P来判断是否存在两个元素之和等于x。low=l;high=n;while(high>low)ifA[low]+A[hig
某软件项目的活动图如下图所示,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,边上的数字表示活动的持续时间(天),则完成该项目的最少时间为________________天。活动FG的松弛时间为________________天。
根据输出对输入的依赖关系设计测试用例的黑盒测试方法是________。
随机试题
第一胎,孕40周,临产已10小时,ROA,胎心100次/min,胎儿监护见频繁晚期减速波型。下述哪种情况有条件立即行阴道助产术(产钳或胎头吸引术)
下列不属于个人史的是
烧伤面积的叙述,哪项不恰当
患者,女性,28岁,孕16周,患妊娠合并心脏病,现症见心悸怔仲,面色不华,头晕目眩,失眠多梦,舌淡,脉细弱。治疗宜用
根据《中华人民共和国药品管理法实施条例》,接受委托生产药品的药品生产企业,必须持有与其受托生产的药品相适应的
(2012年)由m个构件所组成的复合铰链包含转动副的个数为()。
居住区内道路可分为:居住区道路、小区路、组团路和宅间小路四级。居住区道路红线宽度为()。
下列与生活有关的谚语不正确的是()。
802.5标准定义了源路选网桥。它假定每一个结点在发送帧时都已经清楚地知道发往各个目的结点的路由,源结点在发送帧时需要将详细的路由信息放在帧的______。
Youmaysaythatthebusinessofmarkingbooksisgoingtoslowdownyourreading.【C1】________probablywill.That’soneof
最新回复
(
0
)