1 / 10
文档名称:

递归和非递归先中后遍历二叉树.doc

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

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

分享

预览

递归和非递归先中后遍历二叉树.doc

上传人:1136365664 2017/12/17 文件大小:106 KB

下载得到文件列表

递归和非递归先中后遍历二叉树.doc

相关文档

文档介绍

文档介绍:一、设计思想
在本次试验中,主要用两种方法遍历树,一种是递归方法遍历树,另一种是用非递归方法来遍历树。
递归遍历树:
先序遍历二叉树,若二叉树为空,则空操作否则执行,首先,访问根节点,然后先序遍历根结点的左子树,最后先序遍历根节点的右子树。
中序遍历二叉树,若二叉树为空,则空操作否则执行,首先,中序遍历根节点的左子树,然后访问根节点,最后中序遍历根节点的右子树。
后序遍历二叉树,若二叉树为空,则空操作否则执行,首先后序遍历根节点的左子树,然后后序遍历根节点的右子树,最后访问根节点。
非递归遍历:
先序遍历二叉树:①初始化一个栈,存放二叉结点指针。②t(为二叉树结点指针)当t不为空或者栈不为空,重复执行:输出t的数据,并将t入栈,t=t->lchild(循环直到遍历完当前子树的根结点和其左孩子)。③如果栈不为空,弹出栈顶并赋给t,,t=t->rchild。转步骤②。④若栈空,遍历结束。
中序遍历二叉树:①初始化一个栈,用来存放二叉结点指针。②t(为二叉结点指针)当t不为空或者栈不空时,重复执行③④。③当t不为空时,反复执行:将t入栈,t=t->lchild(子树根结点全部入栈)。④t为空但栈不为空,弹栈并赋给t,将t的数据输出,t=t->rchild。
后序遍历二叉树:①初始化一个栈(存放二叉结点)和一个数组(存放标志:进入右子树的标志),栈和数组的下标都为栈指针的值。②当t(为二叉结点指针)当t不为空或者栈不空时,重复执行③④⑤⑥。③当t不为空,反复执行:栈顶指针top加1,t入栈,数组赋值为0,t=t->lchild。④当(>-1)&&([]==1)成立时,反复执行:弹栈顶元素,赋给t,输出t的数据值,栈顶指针要减1。⑤如果栈不空,弹栈顶元素,赋给t,将数组下标为栈顶指针的元素的值设为1,t=t->rchild。⑥如果③④⑤都不成立时,将t赋值为空。
二、算法流程图
先序递归遍历:若二叉树为空,则空操作否则执行,首先,访问根节点,然后先序遍历根结点的左子树,最后先序遍历根节点的右子树。
输出t指向的数据
t为指向根节点的指针变量
开始
t!=null
t=t->lchild
t=t->rchild


结束
图1递归先序遍历二叉树算法流程图
后序递归遍历:若二叉树为空,则空操作否则执行,首先后序遍历根节点的左子树,然后后序遍历根节点的右子树,最后访问根节点。
输出t指向的数据
t为指向根节点的指针变量
开始
t!=null
t=t->lchild
t=t->rchild


结束
图2递归后序遍历二叉树算法流程图
先序非递归遍历:②t(为二叉树结点指针)当t不为空或者栈不为空,重复执行:输出t的数据,并将t入栈,t=t->lchild(循环直到遍历完当前子树的根结点和其左孩子)。③如果栈不为空,弹出栈顶并赋给t,,t=t->rchild。转步骤②。④若栈空,遍历结束。
开始
t!=null||!=-1
t!=null
++;t进栈,t=t->lchild
栈不空
弹栈赋给t, 输出t->data,t=t->lchild





结束
图3非递归先序遍历二叉树算法流程图

最近更新

2025年度农村土地租赁与农业循环经济合作协议.. 8页

2025年度农机租赁与农业保险配套服务合同 9页

2025年排灌机械项目发展计划 67页

2025年工伤保险服务项目建议书 54页

农业物联网在精准灌溉中的应用研究-全面剖析 27页

聚酯瓶制造业的市场结构分析-全面剖析 27页

高二物理电磁波及其应用 26页

某博物馆建设工程BT模式投资建设合同范本 25页

毕业晚会闭幕词范文(25篇) 23页

活力青春魅力校园的演讲稿范文(3篇) 6页

一种土层原地应变(力)测量方法及其实验与现场.. 2页

读完长恨歌心得体会范文(3篇) 7页

过年小学作文 11页

《研究与发展》杂志评选(1986年)获胜项目介绍.. 2页

《丹溪治法心要》中姜汁运用规律初探 2页

“菱形块”类零件的失效分析及选材研究 2页

第四讲招聘与选择 20页

“K—法”中缩合反应过程的初步探讨 2页

读写结合法在高中英语写作教学中的应用研究 2页

Y-Ba-Cu-O系超导体的水解性研究 2页

第8课《柳叶儿》同步练习(苏教版初一下)-(6)d.. 2页

苏卫单招校测2025试卷 9页

《黄河颂》33694省公开课一等奖全国示范课微课.. 29页

部编版九年级语文上册必背古诗文 8页

消毒小车策划书 4页

3D打印技术与虚拟现实的融合 26页

党建调研提纲 2页

雷雨第四幕1 20页

初中信息技术说课万能课件 15页

出_家_剃_度_仪_轨文库 13页