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