如何用栈实现递归与非递归的转换VIP专享VIP免费

第1页共14页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第1页共14页如何用栈实现递归与非递归的转换一.为什么要学习递归与非递归的转换的实现方法?1)并不是每一门语言都支持递归的.2)有助于理解递归的本质.3)有助于理解栈,树等数据结构.二.递归与非递归转换的原理.递归与非递归的转换基于以下的原理:所有的递归程序都可以用树结构表示出来.需要说明的是,这个"原理"并没有经过严格的数学证明,只是我的一个猜想,不过在至少在我遇到的例子中是适用的.学习过树结构的人都知道,有三种方法可以遍历树:前序,中序,后序.理解这三种遍历方式的递归和非递归的表达方式是能够正确实现转换的关键之处,所以我们先来谈谈这个.需要说明的是,这里以特殊的二叉树来说明,不过大多数情况下二叉树已经够用,而且理解了二叉树的遍历,其它的树遍历方式就不难了.1)前序遍历a)递归方式:[code:1:1f2a39cc2d]voidpreorder_recursive(BitreeT)/*先序遍历二叉树的递归算法*/{if(T){visit(T);/*访问当前结点*/preorder_recursive(T->lchild);/*访问左子树*/preorder_recursive(T->rchild);/*访问右子树*/}}[/code:1:1f2a39cc2d]b)非递归方式[code:1:1f2a39cc2d]voidpreorder_nonrecursive(BitreeT)/*先序遍历二叉树的非递归算法*/{initstack(S);push(S,T);/*根指针进栈*/第2页共14页第1页共14页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第2页共14页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:1f2a39cc2d]2)中序遍历a)递归方式[code:1:1f2a39cc2d]voidinorder_recursive(BitreeT)/*中序遍历二叉树的递归算法*/{if(T){inorder_recursive(T->lchild);/*访问左子树*/visit(T);/*访问当前结点*/inorder_recursive(T->rchild);/*访问右子树*/}}[/code:1:1f2a39cc2d]b)非递归方式[code:1:1f2a39cc2d]voidinorder_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);/*向右走一步*/}第3页共14页第2页共14页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第3页共14页}}[/code:1:1f2a39cc2d]3)后序遍历a)递归方式[code:1:1f2a39cc2d]voidpostorder_recursive(BitreeT)/*中序遍历二叉树的递归算法*/{if(T){postorder_recursive(T->lchild);/*访问左子树*/postorder_recursive(T->rchild);/*访问右子树*/visit(T);/*访问当前结点*/}}[/code:1:1f2a39cc2d]b)非递归方式[code:1:1f2a39cc2d]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(a.mark){case0:push(S,{a.ptr,1});/*修改mark域*/if(a.ptr->lchild)push(S,{a.ptr->lchild,0});/*访问左子树*/break;case1:push(S,{a.ptr,2});/*修改mark域*/if(a.ptr->rchild)push(S,{a.ptr->rchild,0});/*访问右子树*/break;case2:visit(a.ptr);/*访问结点*/}第4页共14页第3页共14页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第4页共14页}}[/code:1:1f2a39cc2d]4)如何实现递归与非递归的转换通常,一个函数在调用另一个函数之前,要作如下的事情:a)将实在参数,返回地址等信息传递给被调用函数保存;b)为被调用函数的局部变量分配存储区;c)将控制转移到被调函数的入口.从被调用函数返回调用函数之前,也要做三件事情:a)保存被调函数的计算结果;b)释放被调函数的数据区;c)依照被调函数保存的返回地址将控制转移到调用函数.所有的这些,不论是变量还是地址,本质上来说都是"数据",都是保存在系统所分配的栈中的.ok,到这...