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

最近更新

一机多罐微电脑控制煮糖在金光糖厂通过技术鉴.. 2页

记叙文作文汇编9篇 13页

财务人员本人述职报告(素材下载18篇) 63页

高中感恩主题班会课件《擎起爱的天空》 7页

电子政务绩效评估综述 38页

《灰色预测模型》的推广及应用实例 2页

《棉纺织技术》第十二次编委会在江西举行 2页

《建筑技术通讯》施工技术分册总目录(1979) 2页

《外贸英语口语》理论与实践教学探索 2页

《北方暴雨预报方法》研究课题取得初步成果 2页

“鸡毛换糖再出发”下的地域电商模式研究 2页

“营改增”对信息技术行业的影响浅析 2页

“电镀Ni—Zn活性阴极”通过技术鉴定 2页

“好客山东休闲汇”背景下的滨海休闲安全探讨.. 2页

“功率法测平衡”技术的应用及节能潜力分析 2页

“今日售出 他年还款”的财务决策分析 2页

“K,C”通用公式在中频电热电容器设计中的应用.. 2页

φ76mm三辊轧管机组轧后钢管外径的影响因素探.. 2页

~(125)I-α-银环蛇毒素皮下吸收的研究 2页

ZJCA型磁化节油器在加热炉上的应用 2页

X波段微波平衡调制器的工作原理和调试方法 2页

Woodward调速器简介及在工业汽轮机上的应用 2页

高一10班家长会 19页

UV-Ⅰ型低温消化反应器的研制及应用 2页

UE型乙烯基酯树脂合成工艺计算初探 2页

骨质疏松康复治疗 28页

TFZ-12H型轴带交流发电机实船应用及改姓意见 2页

第三方物流承运服务方案 22页

劳务合同工伤责任条款 5页

建筑资质挂靠协议书3篇 9页