66 lines
1.0 KiB
C++
66 lines
1.0 KiB
C++
// 树形结构的前中后序遍历，以及bfs层级遍历
|
||
#include<bits/stdc++.h>
|
||
using namespace std;
|
||
const int N = 20;
|
||
int ls[N], rs[N];
|
||
// 先序遍历
|
||
void dfs1(int x){
|
||
cout << x << ' ';
|
||
if(ls[x]) dfs1(ls[x]);
|
||
if(rs[x]) dfs1(rs[x]);
|
||
}
|
||
|
||
// 中序遍历
|
||
void dfs2(int x){
|
||
if(ls[x]) dfs2(ls[x]);
|
||
cout << x << ' ';
|
||
if(rs[x]) dfs2(rs[x]);
|
||
}
|
||
|
||
// 后序遍历
|
||
void dfs3(int x){
|
||
if(ls[x]) dfs3(ls[x]);
|
||
if(rs[x]) dfs3(rs[x]);
|
||
cout << x << ' ';
|
||
}
|
||
|
||
// 层序遍历
|
||
void bfs(){
|
||
queue<int> q;
|
||
q.push(1);
|
||
while(q.size()){
|
||
int x = q.front(); q.pop();
|
||
cout << x << ' ';
|
||
if(ls[x]) q.push(ls[x]);
|
||
if(rs[x]) q.push(rs[x]);
|
||
}
|
||
}
|
||
|
||
int main(){
|
||
int n; cin >> n;
|
||
for(int i = 1; i <= n; i++) cin >> ls[i] >> rs[i];
|
||
dfs1(1); cout << endl;
|
||
dfs2(1); cout << endl;
|
||
dfs3(1); cout << endl;
|
||
bfs(); cout << endl;
|
||
return 0;
|
||
}
|
||
/* test samples
|
||
10
|
||
2 3
|
||
4 5
|
||
6 7
|
||
8 0
|
||
0 9
|
||
0 0
|
||
10 0
|
||
0 0
|
||
0 0
|
||
0 0
|
||
out:
|
||
1 2 4 8 5 9 3 6 7 10
|
||
8 4 2 5 9 1 6 3 10 7
|
||
8 4 9 5 2 6 10 7 3 1
|
||
1 2 3 4 5 6 7 8 9 10
|
||
*/
|