[PAT-B] 1099 Build A Binary Search Tree

cpcs

1099 Build A Binary Search Tree

给定树，把二叉搜索树构造出来，再给出层序遍历…… 就直接模拟就行，二叉树的结构是给定的，按中序遍历的顺序由小到大填数即可。

1. #include <cstdio>
   
2. #include <cstring>
   
3. #include <string>
   
4. #include <queue>
   
5. #include <algorithm>
   
6. 
   
7. using namespace std;
   
8. 
   
9. 
   
10. int left[105];
    
11. int right[105];
    
12. int a[105];
    
13. int b[105];
    
14. queue<int> q;
    
15. 
    
16. void dfs(int now, int &x) {
    
17.         if (now < 0) {
    
18.                 return;
    
19.         }
    
20.         dfs(left[now], x);
    
21.         b[now] = a[x++];
    
22.         dfs(right[now], x);
    
23. }
    
24. 
    
25. int main() {
    
26. int n;
    
27.         scanf("%d", &n);
    
28.         for (int i = 0; i < n; ++i) {
    
29.                 scanf("%d%d",&left【i】, &right【i】);
    
30.         }
    
31.         for (int i = 0; i < n; ++i) {
    
32.                 scanf("%d", &a【i】);
    
33.         }
    
34.         sort(a, a + n);
    
35.         dfs(0, n = 0);               
    
36.         bool mark = false;
    
37.         for (q.push(0); !q.empty(); q.pop()) {
    
38.                 if (mark) {
    
39.                         putchar(' ');
    
40.                 }
    
41.                 else {
    
42.                         mark = true;
    
43.                 }
    
44.                 int x = q.front();
    
45.                 printf("%d", b[x]);
    
46.                 if (left[x] >= 0) {
    
47.                         q.push(left[x]);
    
48.                 }
    
49.                 if (right[x] >= 0) {
    
50.                         q.push(right[x]);
    
51.                 }
    
52.         }
    
53.         puts("");
    
54.         return 0;
    
55. }
    

复制代码