1099 Build A Binary Search Tree

 1 #include<iostream>
 2 #include<queue>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 const int maxn = 200;
 7 struct Node {
 8     int data;
 9     int left ,right;
10 } node[maxn];
11 
12 int in[maxn],index = 0;
13 
14 void inorder(int root) { //中序遍历，构造二叉查找树
15     if(root == -1) return ; //叶子节点，直接返回
16     inorder(node[root].left);
17     node[root].data = in[index++];
18     inorder(node[root].right);
19 }
20 
21 int num = 0;
22 void levelorder(int root) {//层序遍历
23     //第一步，定义队列并入队
24     queue<int> que;
25     que.push(root);
26     //第二步，判断队列非空
27     while(!que.empty()) {
28         //第三步，访问队首元素并出队
29         int now = que.front();
30         if(num > 0) printf(" ");
31         printf("%d",node[now].data);
32         num++;
33         que.pop();
34         //第四步，下一层元素（左、右孩子）入队
35         if(node[now].left != -1) que.push(node[now].left);
36         if(node[now].right != -1) que.push(node[now].right);
37     }
38 }
39 
40 int main() {
41     int n;
42     cin>>n;
43     for(int i = 0; i < n; ++i) //构造二叉树
44         cin>>node[i].left>>node[i].right;
45     for(int i = 0; i < n; ++i)
46         cin>>in[i];
47     sort(in,in+n);//递增排序
48     inorder(0); //中序遍历
49     levelorder(0);//层序遍历
50     return 0;
51 }