首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
试编写出先序、中序和后序遍历的非递归算法。
试编写出先序、中序和后序遍历的非递归算法。
admin
2014-12-25
113
问题
试编写出先序、中序和后序遍历的非递归算法。
选项
答案
(1)先序遍历。 void PreOrderTraverse(BiTree bt) { /*二叉树bt采用二叉链表存储,对其进行先序遍历*/ if(bt) /*二叉树非空*/ {InitStack(S);Push(S,bt); while(!EmptyStack(S)) {while(GetTop(S,p)&&p) /*当栈顶元素非空*/ {visit(p一>data); push(S,P一>ichild); Pop(S,P); if(!EmptyStack(S)) /*若栈非空,使栈顶元素的右孩子人栈*/ {Pop(S,p);Push(S,P一>rchild);) } } } (2)中序遍历。 void InOrderTraverse(BiTree bt) { /*二叉树bt采用二叉链表存储,对其进行中序遍历*/ if(bt) {InitStack(s);Push(s,bt); while(!EmptyStack(S)) {while(GetTop(S,p)&&p) push(S,P一>ichild); Pop(S,P); if(!EmptyStack(S)) {Pop(S,P); visit(p一>data); Push(S,P一>rchild); } } } } (3)后序遍历。 voidFeorder(BiTreebt) { /*后序遍历bt所指的二又树,s为存储二叉树结点指针的栈*/ InitStack(S);Push(S,bt); while(!EmptyStack(S)) {while(GetTop(S,P)) Push(S,P一>ichild); Pop(S,P); if(!EmptyStack(S)) {Push(S,GetTop(S,p)一>rchild); if(GetTop(s,P)==NULL) {Pop(s,P);Pop(s,P); visit(P一>data); while(GetTop(s,q)一>rchild==p&&!EmptyStack(s)) {Pop(s,P); visit(P一>data); } if(!EmptyStack(s)) Push(s,GetTop(s,P)一>rchild); } } } }
解析
将一个递归算法转换成一个非递归算法,利用栈就可消除递归,根据对二叉树进行先序、中序和后序遍历的思想,其非递归算法描述如下。
转载请注明原文地址:https://www.kaotiyun.com/show/YeVx777K
本试题收录于:
数据结构导论题库理工类分类
0
数据结构导论
理工类
相关试题推荐
下面是某闭环系统的阶跃响应图,则根据此图可知该系统的特征方程的根【】
网络操作系统按结构可以分为“对等结构操作系统”和“非对等结构操作系统”,请对这两种结构操作系统的主要特点给以简要说明。
下面给出的是一份不完整的HTML文档,请根据HTML的基本语法规则补充填写①、②、③、④处所缺少的标记,并简要说明该文档中的标记<IMGSRC=’’D:/picture.jPg’’>的作用。<HTML><HEAD>
在模块结构图中,用带空心圆的箭头表达()
某项目管理系统的数据库有如下三个关系:音像(音像编号,音像名,租金,类别)会员(会员编号,会员名,年龄,所在地区,联系电话)租借(音像编号,会员编号,租借日期,归还日期)实现下列操作:使用SQL语句查询每一类音像制品的类别和被租借的次数。
某电子公司税后利润的时间序列数据如下表所示:(1)用加权平均数法给出F8的预测值。设权数ω1,…,以分别为1.00,1.32,1.52,1.75,2.01.2.31,2.66。(2)用加权移动平均法计算F5,F6,F7,F8的预测值,设n=4,权数顺
在网络技术中,以结点代表活动,以箭线表示活动之间的先后承接的关系,这种图称之为()
在求最大流量问题中,已知从起点到它相邻的三个结点每分钟最多可通过30,25,40辆汽车,则从终点每分钟可输出的汽车辆数是()
箭线式网络图的结点不_______,不_______。
设二进制符号序列为11100101,试以矩形脉冲为例,分别画出相应的单极性、双极性、单极性归零、双极性归零、差分码。
随机试题
Forthispart,youaresupposedtowriteanessaywiththetitleof"ShouldMenandWomenBeEqual?"inEnglishinatleastwor
关于糖、脂、氨基酸代谢错误的是
病人,男性,65岁,体检发现其上腹部有明显的蠕动波,波形自左向右移动,应考虑为
A.气虚血瘀所致的中风B.瘀血痹阻所致的胸痹心痛C.气滞血瘀所致的胸痹D.肾阳不足,腰膝酸冷E.血虚所致的面色萎黄血府逐瘀口服液主治()。
黑质-纹状体的兴奋递质是
国家的基本社会制度是国家制度体系中的重要内容。根据我国宪法规定,关于国家基本社会制度,下列哪一表述是正确的?(2015年卷一22题)
()是制定会计核算制度以及具体会计准则的依据。
依据《风景名胜区条例》,关于风景名胜区的保护,下列说法中,错误的是()。
每台设备灌浆分为一次灌浆和二次灌浆,一次灌浆是指本设备()。
经济杠杆干预手段和信息诱导手段两者之间的根本差别在于( )。
最新回复
(
0
)