C/C++树遍历的应用-树的重建

71 阅读 0 评论 47 点赞

我是靠谱客的博主能干红酒，这篇文章主要介绍C/C++树遍历的应用-树的重建，现在分享给大家，希望可以做个参考。

输入：
    第1行输入二叉树的结点数
    第2行输入前序遍历的结点编号序列，相邻编号用空格分开
    第3行输入中序遍历的结点编号序列，相邻编号用空格分开

输出：
在1行中输出后序遍历的结点编号序列，用空格分开

代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
int n, pos;
vector<int> pre, in, post;
void rec(int l, int r){
if(l >= r) return;
int root = pre[pos++];
int m = distance(in.begin(), find(in.begin(), in.end(), root));
rec(l, m);
rec(m+1, r);
post.push_back(root);
}
void solve(){
pos = 0;
rec(0, pre.size());
for(int i = 0; i < n; i++){
if(i) cout << " ";
cout << post[i];
}
cout << endl;
}
int main(){
int k;
cin >> n;
for(int i = 0; i < n; i++){
cin >> k;
pre.push_back(k);
}
for(int i = 0; i < n; i++){
cin >> k;
in.push_back(k);
}
solve();
}