首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
自考
试编写出先序、中序和后序遍历的非递归算法。
试编写出先序、中序和后序遍历的非递归算法。
admin
2014-12-25
115
问题
试编写出先序、中序和后序遍历的非递归算法。
选项
答案
(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
数据结构导论
理工类
相关试题推荐
通信双方可以同时发送和接收信息,这种通信方式称为【】
数据在通信系统中的传输方式按二进制数据传输的时空顺序分为【】
_______是以一台数据设备作为中心处理系统,其他的入网设备均与中心处理机通过通信线路相连,其他结点之间不能直接通信,必须通过中心处理机进行转发。
现有如下关系模式:R(教师号,姓名,部门号,部门名称,科研项目编号,项目名称,项目经费,担任工作,完成时间)每名教师可以参加多项科研项目,每个项目可以有多名教师参加,教师参加科研工作包括担任工作及他完成所担任部分的完成时间。(1)根据上述条件,写
SQL3的触发器有时也称为主动规则或事件——条件——________规则。
SQL语言中条件“年龄BETWEEN20AND30”表示年龄在20至30之间,且()
在数据库中为提高查询速度而设置的逻辑排序手段称为________。
在某计算中心的一个单道程序设计系统中,有A、B、C三个作业在等待处理,他们到达系统的时间和估计需计算的时间如下表所示:假定系统从11:30开始调度作业,试问:采用最高响应比优先算法,作业的执行次序以及各作业的周转时间分别为多少?
搭设高度________米及以上的落地式钢管脚手架工程为危险性系数较大的分部分项工程。()
在决策树中,小方框为______结点,它引出的分枝称为______分枝。
随机试题
Wheneverapupilmakesamistake,teachersshouldshowhimhowtocorrectit______punishhim.
心室功能曲线反映下列哪种关系
A.基础培养基B.营养培养基C.鉴别培养基D.选择培养基E.特殊培养基七叶苷水解试验属于
2003年5月14日,三位法学博士致信全国人民代表大会常委会,认为国务院于1982年5月12日颁布的《城市流浪乞讨人员收容遣送办法》与我国宪法和有关法律相抵触,特向全国人大常委会提出审查《城市流浪乞讨人员收容遣送办法》的建议。同年6月18日,温家宝总理主持
向心型城市化阶段的特点是()。
甲无偿保管乙的物品;在保管过程中,由于甲的一般过失,乙的物品发生损毁。根据合同法律的有关规定,下列说法正确的是( )。
人们在遭受强大的自然灾害后可能出现的精神障碍和心理反应包括()。
下列关于中学“腐乳的制作”实验,叙述正确的是()。
A.条件(1)充分,但条件(2)不充分。B.条件(2)充分,但条件(1)不充分。C.条件(1)和条件(2)单独都不充分,但条件(1)和条件(2)联合起来充分。D.条件(1)充分,条件(2)也充分。E.条件(1)和条件(2)单独都不充分,条件(1)和
桌面上有多个打开的窗口,通过对窗口可见部分的操作,将当前窗口切换为“记事本”窗口。
最新回复
(
0
)