1 / 14
文档名称:

递归非递归两种算法遍历二叉树.doc

格式:doc   大小:152KB   页数:14页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

递归非递归两种算法遍历二叉树.doc

上传人:hnxzy51 2020/11/10 文件大小:152 KB

下载得到文件列表

递归非递归两种算法遍历二叉树.doc

相关文档

文档介绍

文档介绍:一、设计思想
1. 用递归算法遍历 
设计思想:主要是通过不同程序顺序,从而实现递归的顺序遍历 
前序遍历:先判断节点是否为空,如果不为空,则输出。再判断左节点是否为空,如果不为空,则递归调用,直到遍历到最左边。接着再遍历最左边的右子树,如果此时右子树不为空,则递归遍历左子树的操作,直到遍历到叶子节点。如果右子树为空,则回溯上次的递归调用,重复输出和遍历右子树的操作。 
中序遍历: 先遍历左节点是否为空,如果不为空,则递归调用,直到遍历到最左边或者叶子节点,然后输出,接着再遍历最左边的右子树,如果此时右子树不为空,则递归重复遍历左子树的操作,直到遍历到叶子节点。如果右子树为空,则回溯到上次递归调用,重复输出和遍历右子树的操作。 
后序遍历:先判断左节点是否为空,如果不为空则一直递归直到遍历到最左边,然后遍历右节点,再接着遍历到左子树的最右边,直到遍历到叶子节点。此时输出,回溯到上次递归,继续执行后面的操作,重复,直到将整个树遍历完毕。 
2. 用非递归算法遍历 
设计思想:主要是通过栈的存取,判空,从而实现树的遍历 
前序遍历:通过一个循环实现。先输出节点的数值,因为栈的特性,则需要先判断右子树是否为空,如果不为空,则将右子树压栈。然后判断左子树是否为空,如果不为空,则将左子树压栈。接着再将栈里面的子树弹出赋给给当前节点变量,重复上述操作,直到栈为空后退出循环。 
中序遍历:通过循环实现。将树一直遍历到最左端,并将中间所经过的节点保存在栈中,当遍历到最左边的时候,则弹出栈里面的子树。输出数值,将当前节点赋值为当前节点的右子树,遍历右子树,即重复上述操作,直到当前节点为空,并且栈元素为0。
 
后序遍历:通过循环和标记栈实现。将数一直遍历到最左端,并将中间的节点保存在树栈中,同时同步的添加一个标记栈。当遍历到最左边的时候,弹栈并赋值给当前栈,然后判断标记栈的数值,如果数值为0的话则代表当前树没有遍历过,遍历右子树。然后重复上面的操作,如果数值为1的话则代表此时数已经遍历过了,可以开始输出了,为了避免重复输出,将当前栈赋为空。重复循环操作,直到栈没有元素,且当前节点为空(因为一直左的操作并没有将右子树压栈)。
开始
Root=null
Y
N
输出数据
=null
Root=Tree t
=null
N
Y
Y
N
结束
开始
Root=Tree t
Root=null
=null
N
N
输出数据
Y
=null
结束
Y
N
开始
Root=Tree t
Root=null
=null
=null
Y
输出数据
结束
Y
Y
Y
N
N
N
二、算法流程图
图1 递归算法-先序遍历 图2 递归算法-后序遍历 图3 递归算法-中序遍历
开始
=
null
Tree t=root
output
t = null
N
Y
Push
=
null
Push
N
Y
N
栈为空
t=
()
Y
N
结束
Y
开始
Tree t=root
压栈
t = null
N
Y
t=current.
getLtree()
t=
()
output
t=current.
getRltree()
栈为空
N
结束
Y
图4 非递归算法-先序遍历 图5 非递归算法-中序遍历
开始
Tree t=root
Push
t = null
N
Y
t=()
标签栈压栈
t=
()
标签栈出栈
赋值给标志位
判断栈是否已经入栈过
N
Y
t=()
标签栈压栈
出栈并赋值t
Output
Current=null
树栈为空且当前节点为空
N
结束
Y
图6 非递归算法-后序遍历
三、源代码
#include<>
#include<>

typedef char ElemType;
//定义树结构
typedef struct tree
{
ElemType data;
struct tree * lchild;
struct tr

最近更新

2025年郑州食品工程职业学院单招职业适应性测.. 63页

2025年郑州澍青医学高等专科学校单招职业倾向.. 63页

2025年郑州工商学院单招职业适应性测试题库完.. 61页

2025年郑州城建职业学院单招职业倾向性测试题.. 63页

2025年郑州医药健康职业学院单招职业适应性测.. 59页

2025年遵义师范学院单招职业适应性测试题库推.. 62页

2025年遂宁工程职业学院单招职业倾向性测试题.. 63页

2025年通化医药健康职业学院单招职业倾向性测.. 62页

2025年通信电子中的通信模块技术 4页

初中音乐教师心得体会6篇 1页

劳动节实践活动心得(3篇) 3页

2025年辽宁铁道职业技术学院单招职业技能测试.. 62页

2025年辽宁轻工职业学院单招职业技能测试题库.. 63页

告别小学作文500字三篇 5页

研发体系建设(许敏) 46页

2025年辽宁省铁岭市单招职业倾向性测试题库及.. 60页

2025年辽宁省营口市单招职业适应性测试题库及.. 62页

2025年辽宁省沈阳市单招职业倾向性测试题库含.. 62页

大学五四青年节策划书(3篇) 13页

2025年辽宁民族师范高等专科学校单招职业适应.. 61页

2025年辽宁广告职业学院单招职业适应性测试题.. 62页

学习《中小学教学基本规范》心得 30页

学校图书室年度工作计划(22篇) 65页

施工项目部组织机构图 1页

配音服务合同 5页

空气净化系统商业计划书 8页

2025年美国飞机事故数据分析报告模板 27页

《一只马蜂》 10页

卫生专业技术人员考核目标 4页

高考英语3500单词配套练习 答案 doc 40页