首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和c函数代码,将应填入 (n) 处的字句写在答题纸的对应栏内。 【说明】 对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点,且每个结点仅访问一次的过程。函数InOrder。()借助栈实现二叉树的非递归中序遍历运算
阅读下列说明和c函数代码,将应填入 (n) 处的字句写在答题纸的对应栏内。 【说明】 对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点,且每个结点仅访问一次的过程。函数InOrder。()借助栈实现二叉树的非递归中序遍历运算
admin
2010-04-08
74
问题
阅读下列说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
将高级语言程序翻译为机器语言程序的过程中,常引入中间代码,其好处是()。
在编码阶段对系统执行的测试类型主要包括单元测试和集成测试,(40)属于单元测试的内容。
用边界值分析法,假定1<X<100,那么X在测试中应取的边界值是(54)。
下述说法错误的是(46)。
编译和解释是实现高级程序设计语言的两种方式,其区别主要在于______。
假设关系R1和R2如下图所示:若进行R1R2运算,则结果集分别为(1)元关系,共有(2)个元组。(1)
为检测系统所能承受的数据容量,应进行()。
某汽车维修公司有部门、员工和顾客等实体,各实体对应的关系模式如下:部门(部门代码,部门名称,电话)员工(员工代码,姓名,部门代码)顾客(顾客号,姓名,年龄,性别)维修(顾客号,故障情况,维修日期,员工代码)假设每个部门允许有多部电话,则电话属性为
已知关系模式:图书(图书编号,图书类型,图书名称,作者,出版社,出版日期,ISBN),图书编号唯一识别一本图书。建立“计算机”类图书的视图Compute-BOOK,并要求进行修改、插入操作时保证该视图只有计算机类的图书。CREATE(1)
随机试题
关于皮质体表感觉区的叙述,下列哪项是错误的
末次月经是2000年8月26日,其预产期应是
根据我国相关法律规定,下列哪些情形下,商务部可决定采取保障措施?
依据《关于抑制部分行业产能过剩和重复建设引导产业健康发展的若干意见》,不属于当前产能过剩、重复建设较为突出产业和行业的是()。
招标人和中标人应当自中标通知书发出之日起()内签署合同。
室内消火栓阀座材料应用不低于()材料制造。
Archer公司发行了500000股面值$10的普通股。当期Archer公司支付的现金股利为$4.00/股,每股收益为$3.20。Archer公司当前股价为$36/股。Archer公司所在行业的平均市盈率为14.00。在与行业均值进行比较时,Archer公
地球上水的总储量为1.39×1018立方米,但目前能被人们生产、生活利用的水只占总储量的0.77%,即约为0.0107×1018立方米,因此我们要节约用水。请将0.0107×1018用科学计数法表示是()。
A.watchB.informationC.withPhrases:A.associated【T1】______a22-minutereductionintheirlifeexpectancyB.livedanaver
设A是m×n矩阵,C是n阶可逆矩阵,矩阵A的秩为r,矩阵B=AC的秩为r1,则()
最新回复
(
0
)