1 / 24
文档名称:

如何用栈实现递归与非递归的转换.docx

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

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

分享

预览

如何用栈实现递归与非递归的转换.docx

上传人:892629196 2020/7/22 文件大小:16 KB

下载得到文件列表

如何用栈实现递归与非递归的转换.docx

文档介绍

文档介绍:?  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)如何实现递归与非递归的转换         通常,一个函数在调用另一个函数之前,要作如

最近更新

超期服役重载交通路面结构性能分析 4页

谈不同级碎岩石轴承比的数值模拟分析方法 3页

规划环境影响评价指标体系初探及实证研究 3页

装配式住宅院落改造,北京,中国 3页

螺杆钟摆钻具快速钻进及防斜打直技术应用 3页

表达技巧之借景抒情、借物抒情、虚实结合课件.. 22页

萃取精馏分离苯环己烷共沸体系模拟与优化 3页

苏州外资制造业增长因素分析模型 3页

2025年度个人投资入股环保新材料研发公司入股.. 7页

2025年室内门行业技术交流与合作合同本月修订.. 9页

脲醛树脂木材胶粘剂的改性研究 4页

聚磷菌胞内聚合物的染色条件优化及染色方法比.. 3页

缩短空分设备启动时间的优化操作 3页

综合物化探方法在460铀钼矿床勘查中的应用 3页

经济发展方式转变中的技术效率测算与分析——.. 3页

纳米材料与技术在机械工程领域的应用研究 3页

糖尿病与结直肠癌的相关性研究进展 3页

管道内电缆外护套故障精确定位及修复技术 3页

立体车库上用的自锁防落装置的设计研究 3页

稀土产业健康发展问题及对策分析 3页

营养素供给量标准 36页

离心式压缩机喘振原因分析及防喘振措施 3页

社交网络商品在线口碑情感信息传播模型研究 3页

矿物掺和料混凝土氯离子扩散性试验研究 3页

石油企业后勤服务工作社会化探讨 3页

自闭症儿童社交训练技巧 52页

脊柱脊髓功能评分标准 24页

苏卫单招校测2025试卷 9页

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

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