1 / 22
文档名称:

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

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

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

分享

预览

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

上传人:0640105 2020/7/20 文件大小:159 KB

下载得到文件列表

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

文档介绍

文档介绍:用递归、非递归两种方法遍历二叉树一、设计思想二叉树的遍历分为三种方式,分别是先序遍历,中序遍历和后序遍历。先序遍历实现的顺序是:根左右,中序遍历实现的是:左根右,后续遍历实现的是:左右根。根据不同的算法分,又分为递归遍历和非递归遍历。递归算法::先序遍历就是首先判断根结点是否为空,为空则停止遍历,不为空则将左子作为新的根结点重新进行上述判断,左子遍历结束后,再将右子作为根结点判断,直至结束。到达每一个结点时,打印该结点数据,即得先序遍历结果。:中序遍历是首先判断该结点是否为空,为空则结束,不为空则将左子作为根结点再进行判断,打印左子,然后打印二叉树的根结点,最后再将右子作为参数进行判断,打印右子,直至结束。:指针到达一个结点时,判断该结点是否为空,为空则停止遍历,不为空则将左子作为新的结点参数进行判断,打印左子。左子判断完成后,将右子作为结点参数传入判断,打印右子。左右子判断完成后打印根结点。非递归算法::首先建立一个栈,当指针到达根结点时,打印根结点,判断根结点是否有左子和右子。有左子和右子的话就打印左子同时将右子入栈,将左子作为新的根结点进行判断,方法同上。若当前结点没有左子,则直接将右子打印,同时将右子作为新的根结点判断。若当前结点没有右子,则打印左子,同时将左子作为新的根结点判断。若当前结点既没有左子也没有右子,则当前结点为叶子结点,此时将从栈中出栈一个元素,作为当前的根结点,打印结点元素,同时将当前结点同样按上述方法判断,依次进行。直至当前结点的左右子都为空,且栈为空时,遍历结束。:首先建立一个栈,首先将指针指向根结点,将根结点入栈,然后将指针指向左子,左子作为新的结点,将新结点入栈,然后再将指针指向当前结点的左子,直至左子为空,则指针返回,出栈一个元素,作为当前结点,打印该结点,然后将指针指向当前结点右子,将右子作为新的结点,结点入栈,再次进行上面的判断,直至当前结点右子也为空,则再出栈一个元素作为当前结点,一直到结束,使得当前结点右子为空,且栈空,遍历结束。:首先从根节点开始遍历,看根节点是否为空,如果根节点不为空,将根节点的元素压入栈中,继续遍历,如果根节点有左子,索引移动到左子,并以左子为根节点继续遍历。如果左子不为空,则索引移动到左子并入栈;如果左子为空,索引移动到栈顶元素所在的节点,如果此节点的右子不为空并且右子没有被访问过,则索引移动到右子,否则访问栈顶元素并输出,并且定义此节点为被访问过得节点,栈顶元素出栈,树节点定义为NULL,继续遍历。二、算法流程图递归算法:-1-用递归、非递归两种方法遍历二叉树创建二叉树调用自身调用对应函数输出结果图1递归算法流程图先序非递归遍历得到根节点输出当前节点当前节点的元判断当前节存是否存在左入栈,当前节移动到左子上不存存在当前节点跳当前节点到右子上是否存在右子不存在当前节出栈,为空不为空栈是否为空结束点为出栈元素2图先序遍历的非递归算法流程图-2-用递归、非递归两种方法遍历二叉树中序非递归遍历:得到根节判断当前节存当前节点的元是否存在左入栈,当前节点移动到左子不存输出当前节当前节点存判断当前节点到右子是否存在右子不存出栈当前不为为栈是否为点为出栈元结素图3中序遍历的非递归算法流程图-3-用递归、非递归两种方法遍历二叉树后序非递归遍历:得到根节点当前节点的元判断当前节存入栈,当前节是否存在左子移动到左子不存存当前节点判断当前节到右子是否存在右子不存输出当前节出栈当前节不为为栈是否为点为出栈结素后序遍历的非递归算法流程图4图-4-用递归、非递归两种方法遍历二叉树三、源代码前序非递归#include<>structelement//用结构体构建二叉树元素{structelement*lchild;intdata;structelement*rchild;};intmain(){inti=1;structelement*stack[30];structelementa,b,c,d,e;//=1;=2;=3;=4;=5;=&b;=&c;=&d;=&e;=0;=0;=0;=0;=0;=0;stack[i]=&a;while(i!=0)//用数组逐个处理二叉树的元素{while(stack[i]!=0)//取左子树直至为空{printf(%d\n,(*(stack[i])).data);//访问元素的数据部分i++;stack[i]=(*(stack[i-1])).lch

最近更新

销售应备财务知识 40页

咸味膨化零食项目人力资源规划与薪酬管理参考.. 6页

员工流失原因 6页

各方向供参考的论文题目 4页

单位制度选集大全【人员管理】 6页

医院护理人力资源管理规定 5页

化工企业安全标准化绩效考核制度范本 3页

初中美术教学中对学生进行美术欣赏教学策略探.. 4页

传承与开拓 6页

公共部门人力资源管理网考题库(已整理) 4页

催化剂设计 5页

低碳经济背景下我国新能源汽车产业发展的对策.. 5页

优化员工绩效考核和评价指标体系方案 4页

企业绩效评价系统的国内外发展历程及未来趋势.. 3页

企业的人事任命书三 4页

企业战略的推动者和实现者联合利华的人力资源.. 5页

企业基层员工绩效考核管理5 4页

企业人力资源绩效考核存在的问题及解决对策探.. 6页

商场装修泉州合同样本 9页

以战略为导向的绩效管理全面整合 5页

医院装修消防工程合同 9页

人力资源部门与员工关系的维护与管理 6页

多边形生成合并及布尔运算算法研究 2页

人力资源经理设定绩效关键指标(KPI)的二十个标.. 28页

人力资源管理英文论文 8页

人力资源管理的现代化趋势 3页

人力资源管理方法在高职院校班级管理中的应用.. 5页

仓储改造小型装修合同范本 9页

2025年辽宁经济职业技术学院单招职业适应性测.. 74页

DB31 T 1363-2022 口腔综合治疗台水路卫生管理.. 18页