首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和c函数代码,将应填入 (n) 处的字句写在答题纸的对应栏内。 【说明】 对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点,且每个结点仅访问一次的过程。函数InOrder。()借助栈实现二叉树的非递归中序遍历运算
阅读下列说明和c函数代码,将应填入 (n) 处的字句写在答题纸的对应栏内。 【说明】 对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点,且每个结点仅访问一次的过程。函数InOrder。()借助栈实现二叉树的非递归中序遍历运算
admin
2010-04-08
48
问题
阅读下列说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
关于软件著作权产生的时间,下面表述正确的是(10)。
某公司内部使用wb.xyz.com.cn作为访问某服务器的地址,其畔wb是______。
用边界值分析法,假定1<X<100,那么X在测试中应取的边界值是(54)。
对现有软件系统中一些数据处理的算法进行改进,以提高效率,从而更快地响应用户的服务要求。这种行为属于____________维护。
V模型是具有代表意义的测试模型,以下理解正确的是______。A.V模型认为测试阶段是与开发阶段并行的B.V模型是软件开发螺旋模型的变种,它反映了测试活动与分析和设计的关系C.V模型造成需求分析阶段隐藏的问题一直到后期的验收测试才被发现D.V模型是
某指令流水线由5段组成,各段所需要的时间如下图所示。连续输入10条指令时的吞吐率为(6)。
对于下面的有向图,其邻接矩阵是一个①的矩阵。采用邻接链表存储时,顶点0的表结点个数为2,顶点3的表结点个数为0,顶点1的表结点个数为②个。①处应填入?
某软件公司项目组的程序员在程序编写完成后均按公司规定撰写文档,并上交公司存档。此情形下,该软件文档著作权应由______享有。
随机试题
Iworkforagroupthatserveschildrenwithdisabilities.Iloveitandaparticular【C1】______todaymakesmeloveitevenmore.
下列关于髓腔形态描述错误的是
善治胃寒呕吐的药物是
以下属于向海关申报时需要提交的基本单证的是()。
A公司为一综合性的生产企业,增值税一般纳税人,适用增值税税率17%。2009年12月发生的下列事项,请按业务顺序分析流转税的处理(计算过程及结果四舍五人保留两位小数):(1)当月按分期收款合同应取得销售款60000元,月底仍未支付;(2)2
贷款安全比率的合理区间(包括房贷)是()。
神经衰弱的患者精神易兴奋不包括()。
In1924America’sNationalResearchCouncilsenttwoengineerstosuperviseaseriesofindustrialexperimentsatalargeteleph
试分析国际主义风格和现代主义设计风格的联系与区别
下列对802.1lb无线局域网的多峰窝漫游工作方式的描述中,错误的是()。
最新回复
(
0
)