二叉树非递归遍历

二叉树非递归遍历

代码

#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<cstring>
using namespace std;

const int maxn=111;

int n;
int lson[maxn],rson[maxn];
int vis[maxn];

int main(){
    scanf("%d",&n);
    memset(lson,-1,sizeof(lson));
    memset(rson,-1,sizeof(rson));
    memset(vis,-1,sizeof(vis));
    for(int i=1;i<=n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        lson[i]=x,rson[i]=y;
    }

    stack<int> st;

    st.push(1);

    /* 先序遍历
    while(!st.empty()){
        int x=st.top();st.pop();
        printf("%d ",x);
        if(rson[x]>0) st.push(rson[x]);
        if(lson[x]>0) st.push(lson[x]);
    }

    */

    /* 中序遍历
    while(!st.empty()){
        int x=st.top(); st.pop();
        if(vis[x]>-1) printf("%d ",x);
        else{
            vis[x]=1;
            if(rson[x]>0) st.push(rson[x]);
            st.push(x);
            if(lson[x]>0) st.push(lson[x]);
        }
    }
    */

    /* 后续遍历 */
    while(!st.empty()){
        int x=st.top(); st.pop();
        if(vis[x]>-1) printf("%d ",x);
        else{
            vis[x]=1;
            st.push(x);
            if(rson[x]>0) st.push(rson[x]);
            if(lson[x]>0) st.push(lson[x]);
        }
    }

    printf("
");
    return 0;
}

/*
7
2 3
4 5
6 7
-1 -1
-1 -1
-1 -1
-1 -1

*/

接一发正经的

#include<iostream>
#include<cstdio>
#include<stack>
using namespace std;

typedef struct node* PBT;
typedef struct node {
    int v;
    PBT lson;
    PBT rson;
    node(int v) {
        this->v=v;
        lson=rson=NULL;
    }
} BT;

void PreSearch(PBT root) {
    printf("%d ",root->v);
    if(root->lson!=NULL) PreSearch(root->lson);
    if(root->rson!=NULL) PreSearch(root->rson);
}

void PreSearchNoRecur(PBT root) {
    stack<PBT> st;
    st.push(root);
    while(!st.empty()) {
        PBT p=st.top();
        st.pop();
        printf("%d ",p->v);
        if(p->rson!=NULL) st.push(p->rson);
        if(p->lson!=NULL) st.push(p->lson);
    }
}

void MidSearch(PBT root) {
    if(root->lson!=NULL) MidSearch(root->lson);
    printf("%d ",root->v);
    if(root->rson!=NULL) MidSearch(root->rson);
}

void MidSearchNoRecur(PBT root){
    stack<PBT> st;
    st.push(root);
    PBT p=root,cur=root;
    while(!st.empty()){
        while(cur->lson){
            st.push(cur->lson);
            cur=cur->lson;
        }
        PBT p=st.top();
        st.pop();
        printf("%d ",p->v);
        if(p->rson){
            st.push(p->rson);
            cur=p->rson;
        }
    }
}

void AftSearch(PBT root) {
    if(root->lson!=NULL) AftSearch(root->lson);
    if(root->rson!=NULL) AftSearch(root->rson);
    printf("%d ",root->v);
}

void AftSearchNoRecur(PBT root){
    stack<PBT> st;
    st.push(root);
    PBT pre=root;
    while(!st.empty()){
        PBT p=st.top();
        if(pre==p->lson||pre==p->rson||(p->lson==NULL&&p->rson==NULL)){
            printf("%d ",p->v);
            st.pop();
            pre=p;
        }else{
            if(p->rson!=NULL) st.push(p->rson);
            if(p->lson!=NULL) st.push(p->lson);
        }
    }
}

void BuildTree(PBT& root) {
    int v;
    scanf("%d",&v);
    if(v<0) return;
    root=new node(v);
    BuildTree(root->lson);
    BuildTree(root->rson);
}

int main() {
    PBT root=NULL;
    BuildTree(root);
    printf("PreSearch:
");
    PreSearch(root);
    printf("
PreSearchNoRecur:
");
    PreSearchNoRecur(root);
    printf("

MidSearch:
");
    MidSearch(root);
    printf("
MidSearchNoRecur:
");
    MidSearchNoRecur(root);
    printf("

AftSearch:
");
    AftSearch(root);
    printf("
AftSearchNoRecur:
");
    AftSearchNoRecur(root);
    return 0;
}

/*
先序输入(-1代表结点不存在)：
1 3 2 -1 -1 5 -1 -1 4 -1 -1
1 2 3 4 -1 -1 -1 -1 -1
1 2 5 -1 -1 6 -1 -1 3 -1 4 -1 -1
*/