怎么做wp网站,建e网室内设计网官网vr全景,Wordpress 免费收款插件,淄博搜索引擎优化【题目来源】https://www.luogu.com.cn/problem/B3642【题目描述】 有一个 n(n≤10^6) 个结点的二叉树。给出每个结点的两个子结点编号#xff08;均不超过 n#xff09;#xff0c;建立一棵二叉树#xff08;根结点的编号为 1#xff09;#xff0c;如果是叶子结点…【题目来源】https://www.luogu.com.cn/problem/B3642【题目描述】 有一个 n(n≤10^6) 个结点的二叉树。给出每个结点的两个子结点编号均不超过 n建立一棵二叉树根结点的编号为 1如果是叶子结点则输入 0 0。 建好树这棵二叉树之后依次求出它的前序、中序、后序列遍历。【输入格式】 第一行一个整数 n表示结点数。 之后 n 行第 i 行两个整数 l、r分别表示结点 i 的左右子结点编号。若 l0 则表示无左子结点r0 同理。【输出格式】 输出三行每行 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 maxn1e65;struct Tree {int le,ri;
} tr[maxn];void pre(int x) {coutx ;int letr[x].le;int ritr[x].ri;if(le) pre(le);if(ri) pre(ri);
}void in(int x) {int letr[x].le;int ritr[x].ri;if(le) in(le);coutx ;if(ri) in(ri);
}void post(int x) {int letr[x].le;int ritr[x].ri;if(le) post(le);if(ri) post(ri);coutx ;
}int main() {int head1;int n;cinn;for(int i1; in; i) {cintr[i].letr[i].ri;}pre(head),coutendl;in(head),coutendl;post(head),coutendl;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 maxn1e65;
const int maxmmaxn1;
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) {coutu ;for(int ih[u]; i!-1; ine[i]) {int je[i];if(j!0) pre(j);}
}void in(int u) {int v10, v21;for(int ih[u]; i!-1; ine[i]) {v1;int je[i];if(j0) continue;if(v12) coutu , v20;in(j);}if(v2) coutu ;
}void post(int u) {for(int ih[u]; i!-1; ine[i]) {int je[i];if(j!0) post(j);}coutu ;
}int main() {memset(h,-1,sizeof h);int head1;int n;cinn;for(int i1; in; i) {int le,ri;cinleri;//Because its head insertion,//so insert the right side firstadd(i,ri);add(i,le);}pre(head),coutendl;in(head),coutendl;post(head),coutendl;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/138681903https://blog.csdn.net/hnjzsyjyj/article/details/127290036
