洛谷 B3642：二叉树的遍历 ← 结构体方法 链式前向星方法

【题目来源】
https://www.luogu.com.cn/problem/B3642

【题目描述】
有一个 n(n≤10^6) 个结点的二叉树。给出每个结点的两个子结点编号（均不超过 n），建立一棵二叉树（根结点的编号为 1），如果是叶子结点，则输入 0 0。
建好树这棵二叉树之后，依次求出它的前序、中序、后序列遍历。

【输入格式】
第一行一个整数 n，表示结点数。
之后 n 行，第 i 行两个整数 l、r，分别表示结点 i 的左右子结点编号。若 l=0 则表示无左子结点，r=0 同理。

【输出格式】
输出三行，每行 n 个数字，用空格隔开。
第一行是这个二叉树的前序遍历。
第二行是这个二叉树的中序遍历。
第三行是这个二叉树的后序遍历。

【输入样例】
7
2 7
4 0
0 0
0 3
0 0
0 5
6 0

【输出样例】
1 2 4 3 7 6 5
4 3 2 1 6 5 7
3 4 2 5 6 7 1

【算法分析】
● 结构体方法，简单易懂。
● 链式前向星方法，复杂烧脑。
链式前向星：https://blog.csdn.net/hnjzsyjyj/article/details/126474608

【算法代码一：结构体方法】

#include <bits/stdc++.h>
using namespace std;const int maxn=1e6+5;struct Tree {int le,ri;
} tr[maxn];void pre(int x) {cout<<x<<" ";int le=tr[x].le;int ri=tr[x].ri;if(le) pre(le);if(ri) pre(ri);
}void in(int x) {int le=tr[x].le;int ri=tr[x].ri;if(le) in(le);cout<<x<<" ";if(ri) in(ri);
}void post(int x) {int le=tr[x].le;int ri=tr[x].ri;if(le) post(le);if(ri) post(ri);cout<<x<<" ";
}int main() {int head=1;int n;cin>>n;for(int i=1; i<=n; i++) {cin>>tr[i].le>>tr[i].ri;}pre(head),cout<<endl;in(head),cout<<endl;post(head),cout<<endl;return 0;
}/*
in:
7
2 7
4 0
0 0
0 3
0 0
0 5
6 0out:
1 2 4 3 7 6 5
4 3 2 1 6 5 7
3 4 2 5 6 7 1
*/

【算法代码二：链式前向星方法】

#include <bits/stdc++.h>
using namespace std;const int maxn=1e6+5;
const int maxm=maxn<<1;
int h[maxn],e[maxm],ne[maxm],idx;void add(int a,int b) {e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}void pre(int u) {cout<<u<<" ";for(int i=h[u]; i!=-1; i=ne[i]) {int j=e[i];if(j!=0) pre(j);}
}void in(int u) {int v1=0, v2=1;for(int i=h[u]; i!=-1; i=ne[i]) {v1++;int j=e[i];if(j==0) continue;if(v1==2) cout<<u<<" ", v2=0;in(j);}if(v2) cout<<u<<" ";
}void post(int u) {for(int i=h[u]; i!=-1; i=ne[i]) {int j=e[i];if(j!=0) post(j);}cout<<u<<" ";
}int main() {memset(h,-1,sizeof h);int head=1;int n;cin>>n;for(int i=1; i<=n; i++) {int le,ri;cin>>le>>ri;//Because it's head insertion,//so insert the right side firstadd(i,ri);add(i,le);}pre(head),cout<<endl;in(head),cout<<endl;post(head),cout<<endl;return 0;
}/*
in:
7
2 7
4 0
0 0
0 3
0 0
0 5
6 0out:
1 2 4 3 7 6 5
4 3 2 1 6 5 7
3 4 2 5 6 7 1
*/

【参考文献】
https://blog.csdn.net/qq_39456436/article/details/138681903
https://blog.csdn.net/hnjzsyjyj/article/details/127290036