首页 > 代码库 > 手写栈（递归转化为非递归）
手写栈（递归转化为非递归）
递归的本质是通过栈来保存状态，然后再次调用自己进入新的状态，然后函数返回的时候回到上次保存的状态。
如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，就是没有回溯过程，所以我们可以直接将尾递归写成循环
更一般的递归，想要转化为非递归，就需要模拟栈（手写栈）的行为。
遍历的递归和非递归实现：
#include<cstdio>#include<stack>using namespace std;struct node{ int id; node *l=NULL,*r=NULL;}a[100];void PreOrderTraverse(node i){//递归先序遍历 printf("%d ",i.id);//输出根 if(i.l)PreOrderTraverse(*i.l);//遍历左子树 if(i.r)PreOrderTraverse(*i.r);//遍历右子树 }void InOrderTraverse(node i){//递归中序遍历 if(i.l)InOrderTraverse(*i.l);//遍历左子树 printf("%d ",i.id);//输出根 if(i.r)InOrderTraverse(*i.r);//遍历右子树 }void PostOrderTraverse(node i){//递归后序遍历 if(i.l)PostOrderTraverse(*i.l);//遍历左子树 if(i.r)PostOrderTraverse(*i.r);//遍历右子树 printf("%d ",i.id);//输出根 }void PreOrderTraverse(node* i){//非递归先序遍历 stack<node>s; node x; while(i||!s.empty()){ while(i){ s.push(*i); printf("%d ",i->id);//输出根 i=i->l;//遍历左子树 } x=s.top();s.pop(); i=x.r;//遍历右子树 }}void InOrderTraverse(node* i){//非递归中序遍历 stack<node>s; node x; while(i||!s.empty()){ while(i){ s.push(*i); i=i->l;//遍历左子树 } x=s.top();s.pop(); printf("%d ",x.id);//输出根 i=x.r;//遍历右子树 }}void PostOrderTraverse(node* i){//非递归后序遍历 stack<pair<node,bool> >s; pair<node,bool> x; while(i||!s.empty()){ while(i){ s.push(make_pair(*i,0)); i=i->l;//遍历左子树 } x=s.top();s.pop(); if(x.second)printf("%d ",x.first.id);//如果右子树遍历过则输出根 else s.push(make_pair(x.first,1)),i=x.first.r;//如果右子树没遍历则遍历右子树 }}int main(){ for(int i=1;i<99;i++){ a[i].id=i; if(i%2)a[i>>1].r=&a[i]; else a[i>>1].l=&a[i]; } InOrderTraverse(a[1]);printf("\n"); InOrderTraverse(&a[1]);printf("\n"); PreOrderTraverse(a[1]);printf("\n"); PreOrderTraverse(&a[1]);printf("\n"); PostOrderTraverse(a[1]);printf("\n"); PostOrderTraverse(&a[1]);printf("\n"); return 0;}
手写栈（递归转化为非递归）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。