分析：
考察BST + 完全二叉树的性质，注意：
（1）：先用排序排好，然后由于是完全二叉树，我们使用中序来建树。
（2）：建好之后，层次遍历可以采用队列。
1 #include <iostream>
2 #include <stdio.h>
3 #include <algorithm>
4 #include <cstring>
5 #include <vector>
6 #include <queue>
7 #include <cmath>
8
9 using namespace std;
10
11 vector<int> vect;
12 vector<int> result;
13
14 struct Node
15 {
16 int value;
17 Node *left;
18 Node *right;
19 }*root;
20
21 Node *In（int level, int ll, int rr）
22 {
23 if （ll > rr） return NULL;
24 int up_level = pow（2, （level - 1）） - 1; //除最后一层外 总共有多少个
25 int Last_level_left = （rr - ll） + 1 - up_level; //最后一层剩下的
26
27 int k = pow（2, （level - 1） - 1）； //最后一层是否布满了左分支
28
29 int left_left;
30 if （Last_level_left >= k） left_left = up_level;
31 else left_left = pow（2, （level - 2）） - 1 + Last_level_left;
32
33 Node *p = new Node（）；
34 p->value = vect[left_left + ll];
35
36 p->left = In（level - 1, ll, ll + left_left - 1）；
37 p->right = In（level - 1, ll + left_left + 1, rr）；
38
39 return p;
40 }
41
42 void level_order（Node *root）
43 {
44 queue<Node *> q;
45 q.push（root）；
46
47 while （！q.empty（））
48 {
49 Node *p = q.front（）；
50 q.pop（）；
51
52 result.push_back（p->value）；
53
54 if （p->left != NULL）
55 q.push（p->left）；
56 if （p->right != NULL）
57 q.push（p->right）；
58 }
59
60 printf（"%d", result[0]）；
61 for （int i = 1; i < result.size（）； i++）
62 printf（" %d", result[i]）；
63 printf（"\n"）；
64 }
65
66
67 int main（）
68 {
69 int n;
70
71 while （cin 》 n）
72 {
73 vect.clear（）；
74 result.clear（）；
75 for （int i = 0; i < n; i++）
76 {
77 int k;
78 cin 》 k;
79 vect.push_back（k）；
80 }
81 sort（vect.begin（）， vect.end（））；
82
83 int level = log2（n） + 1;
84
85 root = In（level, 0, n - 1）；
86 level_order（root）；
87
88 }
89 return 0;
90 }
View Code |