手寫棧（遞歸轉化為非遞歸）

遞歸的本質是通過棧來儲存狀态，然後再次調用自己進入新的狀态，然後函數傳回的時候回到上次儲存的狀态。

如果一個函數中所有遞歸形式的調用都出現在函數的末尾，我們稱這個遞歸函數是尾遞歸的。當遞歸調用是整個函數體中最後執行的語句且它的傳回值不屬于表達式的一部分時，這個遞歸調用就是尾遞歸。尾遞歸函數的特點是在回歸過程中不用做任何操作，就是沒有回溯過程，是以我們可以直接将尾遞歸寫成循環

更一般的遞歸，想要轉化為非遞歸，就需要模拟棧（手寫棧）的行為。

周遊的遞歸和非遞歸實作：

#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;
}      

轉載于:https://www.cnblogs.com/bennettz/p/6726005.html