[UVA] 10410 - Tree Reconstruction
Problem H: Tree Reconstruction
You have just finished a compiler design homework question where you had to find the parse tree of an expression. Unfortunately you left your assignment in the library, but luckily your friend picked it up for you. Instead of e-mailing you the parse tree so that you can rewrite the solution, your friend decides to play a practical joke and sends you just the DFS and BFS trace. Rather than try to redo the entire question you decide to reconstruct the tree.
Input
The input file contains several test cases as described below.The first line of a input is the number n (1 <= n <= 1000) of nodes in the tree. The nodes in the tree are numbered 1, 2, ..., n. The remaining numbers are the BFS traversal followed by the DFS traversal. Note that when a parent was expanded the children were traversed in ascending order.
Output
The output for each case should consist of n lines, one for each node. Each line should start with the node number followed by a colon followed by a list of children in ascending order. If there is more than one solution, any correct answer is acceptable.
Sample Input
8 4 3 5 1 2 8 7 6 4 3 1 7 2 6 5 8
Sample Output
1: 7 2: 6 3: 1 2 4: 3 5 5: 8 6: 7: 8:
Problem Setter: Jonathan Backer
還第一遇到這種給 BFS 順序跟 DFS 順序的題目，
而且還會是多組解，而且不一定是二分樹。
至於要怎麼輸出一組解，我決定用遞迴去切割，根據 BFS 的順序。
舉個範例輸入：
root = 4
3 5 1 2 8 7 6 3 1 7 2 6 5 8會發現 3 5 是 4 的 son child, 接著將 dfs 的順序切割出來
root = 3
1 2 8 7 6
1 7 2 6
會發現 1 2 是 3 的 son child, 繼續做切割。
#include <stdio.h>
#include <string.h>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
int BFS[1005], DFS[1005];
int n;
vector<int> g[1005];
vector<int> sub_dfs[1005];
int root[1005];
int dfs(int nd, int &bidx) {
/*printf("%d %d:\n", nd, bidx);
for(int i = 0; i < sub_dfs[nd].size(); i++)
printf("%d ", sub_dfs[nd][i]);
puts("");*/
int i, x;
for(i = 0; i < sub_dfs[nd].size(); i++) {
if(sub_dfs[nd][i] == BFS[bidx] && bidx < n) {
x = BFS[bidx];
g[nd].push_back(x);
root[x] = nd;
bidx++, i++;
while(bidx < n && i < sub_dfs[nd].size()) {
if(sub_dfs[nd][i] == BFS[bidx])
break;
sub_dfs[x].push_back(sub_dfs[nd][i]);
root[sub_dfs[nd][i]] = x;
i++;
}
i--;
}
}
while(bidx < n)
dfs(root[BFS[bidx]], bidx);
}
void print(int n) {
int i, j;
for(i = 1; i <= n; i++) {
sort(g[i].begin(), g[i].end());
printf("%d:", i);
for(j = 0; j < g[i].size(); j++)
printf(" %d", g[i][j]);
puts("");
}
}
int main() {
int i;
while(scanf("%d", &n) == 1) {
for(i = 0; i < n; i++)
scanf("%d", &BFS[i]);
for(i = 0; i < n; i++)
scanf("%d", &DFS[i]);
for(i = 0; i <= n; i++)
g[i].clear(), sub_dfs[i].clear();
for(i = 1; i < n; i++)
sub_dfs[BFS[0]].push_back(DFS[i]);
int bidx = 1;
dfs(BFS[0], bidx);
print(n);
}
return 0;
}
/*
8
4 3 5 1 2 8 7 6
4 3 1 7 2 6 5 8
*/
Laredo Sector Border Patrol agents conducting checkpoint operations on U.S. Highway 83 apprehended four subjects hidden in toolboxes northwest of Laredo, Texas.
Unfortunately you left your assignment in the library, but luckily your friend picked it up for you.
The content here is quite interesting about trees, I got to know a lot from this site. I am also very interested to know about the best Tree Service, I looked for it but didn’t find anything. I am actually surious to know about it.