<pre><small><small>
A Binary Search Tree (BST) is recursively defined as a binary tree
which has the following properties:
1.The left subtree of a node contains only nodes with
keys less than the node's key.
2.The right subtree of a node contains only nodes with
keys greater than or equal to the node's key.
3.Both the left and right subtrees must also be binary search trees.
<small><small></pre>
<pre><small><small>
A Complete Binary Tree (CBT) is a tree that is completely filled,
with the possible exception of the bottom level,
which is filled from left to right.
Now given a sequence of distinct non-negative integer keys,
a unique BST can be constructed
if it is required that the tree must also be a CBT.
You are supposed to output
the level order traversal sequence of this BST.
<small><small></pre>
<pre><small><small>
Input Specification:
Each input file contains one test case.
For each case, the first line contains a positive integer N (<=1000).
Then N distinct non-negative integer keys are given in the next line.
All the numbers in a line are separated by a space
and are no greater than 2000.
Output Specification:
For each test case,
print in one line the level order traversal sequence of
the corresponding complete binary search tree.
All the numbers in a line must be separated by a space,
and there must be no extra space at the end of the line.
<small><small></pre>
<pre><small><small>
Sample Input:
10
1 2 3 4 5 6 7 8 9 0
Sample Output:
6 3 8 1 5 7 9 0 2 4
<small><small></pre>
<pre><small><small>

include <stdio.h>

include <stdlib.h>

int compare(const void *a, const void *b);
void Solve(int ALeft, int ARight, int TRoot, int A[], int T[]);
int Get_Left_Nodes(int n);
int Min(int a, int b);
<small><small></pre>
<pre><small><small>
int main(int argc, char const *argv[])
{
// freopen("test.txt", "r", stdin);
int N, tmp;
scanf("%d", &N);
int A[N], T[N];
for (int i = 0; i < N; ++i){
scanf("%d", &tmp);
A[i] = tmp;
}
qsort(A, N, sizeof(int), compare);
int ALeft = 0, ARight = N -1, TRoot = 0;
Solve(ALeft, ARight, TRoot, A, T);
for (int i = 0; i < N; ++i){
if(i == 0){
printf("%d", T[i]);
}
else
printf(" %d", T[i]);
}
return 0;
}
<small><small></pre>
<pre><small><small>
int compare(const void *a, const void *b)
{
return (int)a - (int)b;
}
<small><small></pre>
<pre><small><small>
void Solve(int ALeft, int ARight, int TRoot, int A[], int T[])
{
int n;
n = ARight - ALeft + 1; //结点数n
if(n == 0)
return;
int L, LeftTRoot, RightTRoot;
L = Get_Left_Nodes(n); //计算出n个结点的完全二叉树的左子树的结点个数
T[TRoot] = A[ALeft + L];
LeftTRoot = TRoot * 2 + 1;
RightTRoot = LeftTRoot + 1;
Solve(ALeft, ALeft + L - 1, LeftTRoot, A, T);
Solve(ALeft + L + 1, ARight, RightTRoot, A, T);//Aleft不要忘了+1
}
<small><small></pre>
<pre><small><small>
int Get_Left_Nodes(int n)
{
int H = 0, tmp = 1, X, L;//X为左子树最下一层的结点数
int N = n;
while(N > 1){
N /= 2;
H++;//树的高度
}
for (int i = 0; i < H - 1; ++i){
tmp *= 2;
}
X = n - 2 * tmp + 1;
X = Min( X, tmp );
L = tmp - 1 + X;
return L;
}
<small><small></pre>
<pre><small><small>
int Min(int a, int b)
{
return (a < b) ? a : b;
}
<small><small></pre>