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

最近更新

管理者过度自信与企业会计决策研究述评 3页

简述社保基金投资管理现状及其思考 3页

等离子体中活性粒子分析及化学动力学机理 4页

第三方物流供应商评价选择研究 4页

立式电动刀架刀位检测常见三种方式的比较分析.. 3页

窄河道普通稠油油藏见水规律研究 3页

空间外差光谱仪实验室定标技术研究 3页

工艺品雕刻工-高级(玉雕)300道题目 46页

第六届粤港澳大湾区“粤菜师傅”技能大赛中式.. 15页

移功计算技术带队 3页

秦岭输水隧洞施工期废水水质评价及工艺研究 4页

科学深井井壁稳定性机理分析及方法研究 3页

福建省高端装备制造业技术创新效率评价 3页

禁忌搜索算法及其在TSP问题中的应用研究 4页

2025全国小升初数学应用题精粹100例 86页

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

磁流变抛光技术 3页

碳纳米管功能化表面修饰研究进展 3页

碱性蛋白酶在真丝罗织物前处理中的应用 3页

硫酸钙晶须改性PCABS合金材料的性能研究 3页

药物依赖与戒断 24页

矿用风速传感器检测校准方法分析 3页

矿山支护巡检管理系统的设计与研究 3页

矿井大巷运输系统改造综合效益研究 3页

石油钻井钢管车螺纹加工微乳液的研制与应用 3页

石油化工企业的安全评价技术方法及意义研究 3页

草坪的营养管理 33页

英语规范书写大赛 6页

苏卫单招校测2025试卷 9页

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