1099 Build A Binary Search Tree (30分)(BST的层序或者中序遍历建树，层序便利输出树)

1099 Build A Binary Search Tree (30分)

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
Both the left and right subtrees must also be binary search trees.

Given the structure of a binary tree and a sequence of distinct integer keys, there is only one way to fill these keys into the tree so that the resulting tree satisfies the definition of a BST. You are supposed to output the level order traversal sequence of that tree. The sample is illustrated by Figure 1 and 2.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer

Output Specification:

For each test case, print in one line the level order traversal sequence of that tree. All the numbers must be separated by a space, with no extra space at the end of the line.

Sample Input:

9
1 6
2 3
-1 -1
-1 4
5 -1
-1 -1
7 -1
-1 8
-1 -1
73 45 11 58 82 25 67 38 42

Sample Output:

58 25 82 11 38 67 45 73 42

这题我一开始的思路是先按照给出的节点数据层序遍历建树，这次建树是为了固定BST每个节点的位置。由于BST的中序遍历就是
元素值的排序，因此我们将读入的值排序，然后中序遍历之前固定位置用的那棵树，再将值一一插入。最后层序输出。

层序遍历的代码上面有个需要注意的地方。如果你要将一个节点加入队列，那你必将先为这个节点开辟空间再将其加入，坚决不
能先加入队列，然后再分配空间。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <queue>
 5 using namespace std;
 6 
 7 struct Tree {
 8     int data;
 9     Tree *l, *r;
10 } *root;
11 typedef Tree* ptree;
12 
13 int n, lc, rc;
14 
15 vector <int> ans;
16 
17 typedef pair <int, int> pii;
18 
19 pii vec[100 + 5];
20 
21 void level(ptree &root) {
22     queue <ptree> que;
23     root = new Tree;
24     root -> data = 0;
25     root -> l = root -> r = NULL;
26     que.push(root);
27     while(!que.empty()) {
28         ptree now = que.front(), temp;
29         int k = now -> data;
30         que.pop();
31         lc = vec[k].first, rc = vec[k].second;
32         if(~lc) {
33             temp = new Tree;
34             temp -> data = lc;
35             temp -> l = temp -> r = NULL;
36             now -> l = temp;
37             que.push(temp);
38         }
39         if(~rc) {
40             temp = new Tree;
41             temp -> data = rc;
42             temp -> l = temp -> r = NULL;
43             now -> r = temp;
44             que.push(temp);
45         }
46     }
47 }
48 
49 int val[100 + 5];
50 
51 int cnt;
52 
53 void inorder(ptree &root) {
54     if(root == NULL) {
55         return;
56     }
57     inorder(root -> l);
58     root -> data = val[cnt ++];
59     inorder(root -> r);
60 }
61 
62 void levelorder(ptree root) {
63     if(root == NULL) return;
64     queue <ptree> que;
65     que.push(root);
66     while(!que.empty()) {
67         ptree now = que.front();
68         que.pop();
69         ans.push_back(now -> data);
70         if(now -> l) que.push(now -> l);
71         if(now -> r) que.push(now -> r);
72     }
73 }
74 
75 int main() {
76     scanf("%d", &n);
77     for(int i = 0; i < n; i ++) {
78         scanf("%d %d", &lc, &rc);
79         vec[i] = make_pair(lc, rc);
80     }
81     level(root);
82     for(int i = 0; i < n; i ++) {
83         scanf("%d", &val[i]);
84     }
85     sort(val, val + n);
86     inorder(root);
87     levelorder(root);
88     for(int i = 0; i < ans.size(); i ++) {
89         if(i) printf(" ");
90         printf("%d", ans[i]);
91     }
92     printf("
");
93     return 0;
94 }

是的，上面的是我这种蠢人的做法。。。
AC了之后看到别人直接中序遍历建树，我吐了。
为什么是直接中序遍历建树呢？

我们一开始读入了从0 ~ n所有节点的左右儿子的idx。
然后如果我们用刚刚读入的数据从idx[0]直接开始中序遍历建树，因为如果中序遍历建树，那么我们就可以直接在访问到一个节点的
时候把值赋给他。因此并不需要先层序遍历确定树的结构，因为你中序建树用的也是这些节点，你建的树模子和层序建的树一模一样
，因此你只需要在中序建树的时候顺便把相应的值赋给他就ok了。代码就不实现了吧。直接递归建，数据小。