先序，中序，后序 递归写法

序代表根，先序就是先根，其他类似。每个节点只有作为根时才会取值。

遍历二叉树时，永远都是取根的值，处理根的值，左右子树是用来判断该如果处理它们的根。

构造二叉树的方法

构造n个节点的二叉树，节点编号从1到n
先输入n，从1开始依次输入当前节点的左右节点。
空节点用编号0表示。
参考结构体指针的写法

#include <cstdio>
using namespace std;
const int N=1e5+10;
int n,l[N],r[N];
void pre(int x){
    if(!x) return;
    printf("%d",x);
    pre(l[x]);
    pre(r[x]);
}
void in(int x){
    if(!x) return;
    in(l[x]);
    printf("%d",x);
    in(r[x]);
}
void post(int x){
    if(!x) return;
    post(l[x]);
    post(r[x]);
    printf("%d",x);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&l[i],&r[i]);
    }
    pre(1);
    printf("\n");
    in(1);
    printf("\n");
    post(1);
    printf("\n");

    return 0;
}

测试输入输出，说明及输出：

输入：
8   //共8个节点
2 3 //节点1的左右子树
4 5 //节点2的左右子树
6 0
0 0
7 8
0 0 //节点6左右子树都是0，故是叶子节点
0 0
0 0
输出：
12457836
42758163
47852631

先序，中序，后序 栈写法

#include <cstdio>
#include <stack>
using namespace std;
const int N=1e5+10;
int n,l[N],r[N];
void pre(int x){
    if(!x) return;
    stack<int> stk;
    while(x || !stk.empty()){
        while(x){
            printf("%d",x);
            stk.push(x);
            x=l[x];
        }
        x=stk.top();
        stk.pop();
        x=r[x];
    }
}
void in(int x){
    if(!x) return;
    stack<int> stk;
    while(x || !stk.empty()){
        while(x){
            stk.push(x);
            x=l[x];
        }
        x=stk.top();
        stk.pop();
        printf("%d",x);
        x=r[x];
    }
}
void post(int x){
    if(!x) return;
    stack<int> stk;
    int prev=0;
    while(x || !stk.empty()){
        while(x){
            stk.push(x);
            x=l[x];
        }
        x=stk.top();
        stk.pop();
        if(!r[x]||r[x]==prev){
            printf("%d",x);
            prev=x;
            x=0;
        }
        else{
            stk.push(x);
            x=r[x];
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&l[i],&r[i]);
    }
    pre(1);
    printf("\n");
    in(1);
    printf("\n");
    post(1);
    printf("\n");
    return 0;
}

层次遍历 《使用队列》

#include <cstdio>
#include <queue>
using namespace std;
const int N=1e5+10;
int n,l[N],r[N];
void level(int x){
    if(!x) return;
    queue<int> q;
    q.push(x);
    while(!q.empty()){
        int n=q.size();
        for(int i=0;i<n;i++){
            x=q.front();
            q.pop();
            printf("%d",x);
            if(l[x]) q.push(l[x]);
            if(r[x]) q.push(r[x]);
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&l[i],&r[i]);
    }
    level(1);
    printf("\n");
    return 0;
}

输入输出：

8
2 3
4 5
6 0
0 0
7 8
0 0
0 0
0 0
12345678