首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
试编写出先序、中序和后序遍历的非递归算法。
试编写出先序、中序和后序遍历的非递归算法。
admin
2014-12-25
116
问题
试编写出先序、中序和后序遍历的非递归算法。
选项
答案
(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
数据结构导论
理工类
相关试题推荐
如图所示二阶系统框图,在单位阶跃输入信号作用下,当系统的阻尼比ζ满足什么条件时,二阶系统特征方程的根为两个不相等的负实根?
按拓扑结构来分类,计算机网络可分为息线型网络、环形网络、______、树形网络和网状网络。
实现逻辑隔离的主要方法是_______。
TCP(传输控制协议)是一种面向连接的、可靠的、基于______的传输层通信协议,由IETF的RFC793定义。
在对象联系图中,表示两个属性之间值的联系为逆联系的是()
存放在磁盘上的文件以链接结构组织,假定磁盘的分块大小为每块512字节,而文件的逻辑记录的大小为每个记录250字节。现有一个文件共有10个逻辑记录,采用成组操作,2个逻辑记录为一组,则当主存缓冲区大小为512个字节时,要读出第7个逻辑记录应启动磁盘
若某磁盘共有200个柱面,其编号为0至199,假设正在访问90号柱面,还有若干个请求者在等待服务,他们依次要访问的柱面号为:175、52、157、36、159,则采用先来先服务调度算法,移动臂需移动的距离为_______。
若某计算问题的执行情况如下图:请回答下列问题:简述该计算问题中处理器、输入机和打印机是如何协同工作的。
布雷顿森林体系是以哪种货币为主要国际储备的
设F、C是二叉树中的两个结点,若F是C的祖先结点,则在采用后根遍历方法遍历该二叉树时,F和C的位置关系为:F必定在C的_______。
随机试题
对于曲线,下列各性态不正确的是()。
边界层分离现象的重要后果是下述哪一条?
下列占用耕地中,减按每平方米2元的税额征收耕地占用税的是()。
下列名人中是回族的有()。
国家、地方或学校规定学生必须学习的课程属于()。
我们到了脑筋疲倦的时候,往往随意地将课本以外的书籍取来阅看,______这书籍就成了常和我们亲近的一种消遣品。______我们______以它当作消遣品,没有什么大关系,也就没有严格的选择。填入横线部分最恰当的一项是()。
在横线处填入短语,顺序最恰当的一项是:保护动物,已不是人们陌生的话题。人类的发展,也早已达到可以把其他动物玩弄于掌中并主宰它们命运的程度,但当______、______、______、______的时候,人类真正考虑过动物和人在生命意义上的平等吗
设随机变量X~N(μ.σ2),其分布函数为F(x),又Y=F(X),则P{Y≤}等于().
属于面向对象、解释型程序设计语言的是()
传统中国装饰绳结,也就是我们所说的中国结(Chineseknot),是一种典型的中国本土艺术。这是一门独特的传统中国民间手工编织艺术,每个绳结只使用一根线,根据其形状和意思而命名。在中国,“结”意味着团结、友谊、和平、温暖和爱情等。中国结经常被用来表达良
最新回复
(
0
)