首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
试编写出先序、中序和后序遍历的非递归算法。
试编写出先序、中序和后序遍历的非递归算法。
admin
2014-12-25
31
问题
试编写出先序、中序和后序遍历的非递归算法。
选项
答案
(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://kaotiyun.com/show/YeVx777K
本试题收录于:
数据结构导论题库理工类分类
0
数据结构导论
理工类
相关试题推荐
单位阶跃函数的拉氏变换为________。
按拓扑结构来分类,计算机网络可分为息线型网络、环形网络、______、树形网络和网状网络。
ISO提出的基于______的管理框架是现代网络管理体系结构的核心。
某项目管理系统的数据库有如下三个关系:音像(音像编号,音像名,租金,类别)会员(会员编号,会员名,年龄,所在地区,联系电话)租借(音像编号,会员编号,租借日期,归还日期)实现下列操作:使用SQL语言建立一个有关“科幻”类音像制品的视图VLM,该
设有两个关系模式:职工(职工号,姓名,性别,年龄,职务,工资,部门号)部门(部门号,部门名称,经理名,地址,电话)依据上述关系回答下面小题。用关系代数表达式写出下列查询:检索“采购部”女职工的职工号和姓名。
有4个关系模式如下:出版社(出版社编号,出版社名称)图书(图书编号,书名,出版社编号,定价)作者(作者编号,姓名)著书(图书编号,作者编号,作者排序)注:作者排序-1表示第一作者,依此类推。用SQL语句,完成小题
有4个关系模式如下:出版社(出版社编号,出版社名称)图书(图书编号,书名,出版社编号,定价)作者(作者编号,姓名)著书(图书编号,作者编号,作者排序)注:作者排序-1表示第一作者,依此类推,其中:(1)每
考虑一个涉及如下磁道的按时间有序地请求访问序列:98,183,37,122,14,124,65,67如果磁头的初始位置在53磁道:若接先来先服务算法,服务完上述请求序列后,磁头总计要移动多少个磁道?
试编写出先序、中序和后序遍历的非递归算法。
随机试题
下列选项中,由原发性肺结核引起的是
颅内动脉瘤最常见的部位是()。
下列古代名言中,是对会计职业道德中诚实守信这一重要内容的表述的有()。
甲公司是我国一家历史悠久的老字号餐饮企业。下列各项中,属于甲公司战略分析时需要关注的企业资源有()。
TheEnglishCornerinZhongshanParkiswherepeople【M1】______gotopractisetheirspeakingEnglish.EverySundayafternoon【M2】
根据上图,下列说法正确的是()。
下列罪犯中不能一律认定为首要分子的是()。
假如接到国家人力资源和社会保障部办公厅的通知,一个月后人保部将派考察组前来省里调查民营企业的人才状况。如果省人力资源和社会保障厅领导要你承办这件事,你将如何做好这一工作?
“生命中曾经有过的所有灿烂,终究都需要用寂寞来偿还。”这句话出自()。
数据流图用于抽象描述一个软件的逻辑模型,数据流图由一些特定的图符构成。下面图符名标识的图符不属于数据流图合法图符的是
最新回复
(
0
)