1 / 24
文档名称:

怎样用栈实现递归与非递归的转换.doc

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

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

分享

预览

怎样用栈实现递归与非递归的转换.doc

上传人:﹎多多Dad 2020/3/3 文件大小:35 KB

下载得到文件列表

怎样用栈实现递归与非递归的转换.doc

相关文档

文档介绍

文档介绍:?  1)并不是每一门语言都支持递归的.  2)有助于理解递归的本质.  3)有助于理解栈,.  递归与非递归的转换基于以下的原理:,那个"原理"并没有通过严格的数学证明,只是我的一个猜想,只是在至少在我遇到的例子中是适用的.  学习过树结构的人都明白,有三种方法能够遍历树:前序,中序,,,那个地点以专门的二叉树来讲明,只是大多数情况下二叉树差不多够用,而且理解了二叉树的遍历,)前序遍历a)递归方式:[code:1:2d]voidpreorder_recursive(BitreeT)/*先序遍历二叉树的递归算法*/{if(T){visit(T); /*访问当前结点*/preorder_recursive(T->lchild);/*访问左子树*/preorder_recursive(T->rchild);/*访问右子树*/}}[/code:1:2d]b)非递归方式[code:1:2d]voidpreorder_nonrecursive(BitreeT)/*先序遍历二叉树的非递归算法*/{initstack(S);push(S,T); /*根指针进栈*/while(!stackempty(S)){while(gettop(S,p)&&p){/*向左走到尽头*/visit(p);/*每向前走一步都访问当前结点*/push(S,p->lchild);}pop(S,p);if(!stackempty(S)){/*向右走一步*/pop(S,p);push(S,p->rchild); }}}[/code:1:2d]2)中序遍历a)递归方式[code:1:2d]voidinorder_recursive(BitreeT)/*中序遍历二叉树的递归算法*/{if(T){inorder_recursive(T->lchild);/*访问左子树*/visit(T); /*访问当前结点*/inorder_recursive(T->rchild);/*访问右子树*/}}[/code:1:2d]b)非递归方式[code:1:2d]void inorder_nonrecursive(BitreeT){initstack(S);/*初始化栈*/push(S,T);/*根指针入栈*/while(!stackempty(S)){while(gettop(S,p)&&p) /*向左走到尽头*/push(S,p->lchild);pop(S,p);/*空指针退栈*/if(!stackempty(S)){pop(S,p);visit(p);/*访问当前结点*/push(S,p->rchild);/*向右走一步*/}}}[/code:1:2d]3)后序遍历a)递归方式[code:1:2d]voidpostorder_recursive(BitreeT)/*中序遍历二叉树的递归算法*/{  if(T){  postorder_recursive(T->lchild);/*访问左子树*/  postorder_recursive(T->rchild);/*访问右子树*/  visit(T); /*访问当前结点*/  }}[/code:1:2d]b)非递归方式[code:1:2d]typedefstruct{BTNode*ptr;enum{0,1,2}mark;}PMType; /*有mark域的结点指针类型*/voidpostorder_nonrecursive(BiTreeT)/*后续遍历二叉树的非递归算法*/{PMTypea;initstack(S); /*S的元素为PMType类型*/push(S,{T,0}); /*根结点入栈*/while(!stackempty(S)){pop(S,a);switch(){case0:push(S,{,1}); /*修改mark域*/if(->lchild) push(S,{->lchild,0});/*访问左子树*/break;case1:push(S,{,2}); /*修改mark域*/if(->rchild) push(S,{->rchild,0});/*访问右子树*/break;case2:visit(); /*访问结点*/}}}[/code:1:2d]      4)如何实现递归与非递归的转换         通常,一个函数在调用另一个函数之前

最近更新

《物种起源绪论》 25页

《无创通气的应用》 49页

酒店服务质量评估模型-全面剖析 35页

游戏UI设计与实现-全面剖析 35页

《痛风的治疗体会》 35页

充入Kr-Ar-Ne对改善紧凑型荧光灯性能的探讨 2页

倒频谱分析及其在齿轮故障诊断中的应用 2页

便携式录象机电池的正确使用方法 2页

体育场馆中LED显示屏的应用及检测 2页

低渗透油田精细注水水处理技术 2页

照顾老人住家合同范本:正式保姆服务合同 5页

企业推行精细化管理的方法与技巧 2页

任家庄洗煤厂预先脱泥分选工艺技术实践 2页

以杜仲胶渣作填料的PVC复合材料的研究 2页

从西伯利亚长剖面得到的岩石圈研究结果 2页

《认识角》说课课件 21页

消防设施安装改造工程合同样本 7页

海运合同:全球货物运输新动向 7页

人工弯道式引水枢纽的布置及其计算问题的研究.. 2页

产权式商铺售后返租经营模式的合法性分析 2页

交互式电子技术手册中关键技术的研究 2页

五里营井水位脉动(冲)异常成因初探 2页

云南腾冲盆地硅藻土中有机质的初步研究 2页

汽车润滑油产品采购合同 6页

二十年来日本公路桥梁技术发展简介 2页

乡镇企业会计核算若干问题初探 2页

水利水电工程EPC总承包合同范本 6页

丹江口水电厂1、2号机水导轴承改造 2页

民俗艺术巡回展演合同书 6页

残损货品处理合同细则 6页