首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
试编写出先序、中序和后序遍历的非递归算法。
试编写出先序、中序和后序遍历的非递归算法。
admin
2014-12-25
47
问题
试编写出先序、中序和后序遍历的非递归算法。
选项
答案
(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
数据结构导论
理工类
相关试题推荐
系统的频率特性和系统的传递函数G(s)有密切的联系,令G(s)中的s=________,当叫从0→∞范围变化时,就可求出系统的频率特性。
对于A类地址,其可指派的网络号个数为______个。
______是指在终端或者网络中间结点,计算机设备每秒向网络中发送多少比特数据,其反映的主要是网络设备的性能。
某IP地址为202.194.20.138/27,则该地址块中共有【】个地址。
在SQL/CLI中,将宿主程序与数据库交互的有关信息记录在运行时数据结果中的是()
文件WJ共有4条记录,每个物理块中存放一个物理记录。它采用的链接结构如下图所示。请画出:删除记录1后的链接结构图;
在求最大流量问题中,已知从起点到它相邻的三个结点每分钟最多可通过30,25,40辆汽车,则从终点每分钟可输出的汽车辆数是()
指出布雷顿森林体系内在不稳定性的是
随机试题
按圈闭成因类型分类,油气藏可分为构造油气藏、地层油气藏、()油气藏三大类。
关于糖在小肠被吸收的叙述,正确的是
红细胞进入血液后的平均寿命为
在饱和的软弱地层中进行地铁车站盖挖顺作法施工,首选的挡土结构为()。
下列说法中正确的是()。根据《合同法》规定,下列给出了有关缔约过失责任的构成要件,其中不包括()。
施工成本控制不包括( )。
Recently,Jimhaslostallhis____________.
森林:树木
考核:是指各级行政机关根据法定的管理权限,在一定的时间内,对公务员的工作成绩和服务情形进行定期和不定期的考核与评价。根据上述定义,下列属于考核的是:
假定建立了一个工程,该工程包括两个窗体,其名称(Name属性)分别为Form1和Form2,启动窗体为Form1。在Form1画一个命令按钮Command1,程序运行后,要求当单击该命令按钮时,Form1窗体消失,显示窗体Form2,请在【】和【
最新回复
(
0
)