1064 Complete 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.

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.

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.

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

题目描述：给一棵完全二叉搜索树（满二叉搜索树），求输出它的层序遍历。

二叉搜索树的性质：

1、左子结点权值小于其父结点的权值

2、右子结点权值大于其父结点的权值

3、每个左右子结点都是二叉搜索树

输入：第一行n表示结点个数，第二行表示结点的权值。

输出：输出其层序遍历的结果

解题思路：不需要建树。先将各个结点的权值保存到数组中，接着将数组从小到大排序，以便放入正确的层序遍历数组中。通常将树放入数组中时，都会牺牲0号索引，从索引1开始存储。用递归算法就能获得层序遍历的结果，接下来利用题目给出的例子分析下这个递归算法。

样例构建出来的树长这样：

根据上图，可得到层序遍历数组：

现在模拟递归算法的过程：

n = 10

1. root = 1，root<=n为true，进入if语句中---后续还未完成

2. 执行get_level(root*2)，即get_level(1*2)，root=2，root<=n为true，进入if语句中---后续还未完成

3. 执行get_level(root*2)，即get_level(2*2)，root=4，root<=n为true，进入if语句中---后续还未完成

4. 执行get_level(root*2)，即get_level(4*2)，root=8，root<=n为true，进入if语句中---后续还未完成

5. 执行get_level(roo*2)，即get_level(8*2)，root=16，root<=n为false！步骤 5)执行完毕。返回上一条语句，即步骤 4)，执行未完成的部分。

这时，步骤5) 返回到 步骤 4) 的后续执行步骤，root=8且c=0，level[root]=v[c++]即level[8]=v[0]，且c=1。

6. 接着往下执行，root = 8， get_level(root*2+1)，即get_level(8*2+1)---步骤6)只是个过渡，已完成。

7. get_level(17)，root = 17，root<=n为false！步骤7) 执行完毕。至此，步骤4才真正执行完毕。返回上一条语句，即步骤 3)，执行未完成的部分。

这时，步骤7) 返回到 步骤3) 的后续执行步骤，root=4且c=1，level[root]=v[c++]即level[4]=v[1]，且c=2。

8. 接着往下执行，root = 4，get_level(root*2+1)，即get_level(4*2+1)---步骤8)只是个过渡，已完成。

9. get_level(9)，root = 9，root<=n为true，进入if语句中---后续还未完成

10. 执行get_level(root*2)，即get_level(9*2)，root=18，root<=n为false！步骤10) 执行完毕。返回到上一条语句，即步骤9)，执行未完成部分

这时，步骤10) 返回到 步骤 9)的后续执行步骤，root=9且c=2，level[root]=v[c++]即level[9]=v[2]，且c=3。

11. 接着往下执行，root = 9，get_level(root*2+1)，即get_level(9*2+1)---步骤11)只是个过渡，已完成。

12. get_level(19)，root = 19，root<=n为false！至此，步骤 9)执行完毕，步骤3)也执行完毕。---步骤12)只是个过渡，已完成。

13. 步骤12) 执行完比后，会返回上一个为执行完成的步骤，即步骤2)，往后以此类推。。。

上述过程写的看似复杂，但是自己动手把数据带入进去，模拟一下就也就那么回事，不难不难。

#include<bits/stdc++.h>
using namespace std;
int n, c=0;
vector<int> level, v;
void get_level(int root){
	if(root<=n){
		get_level(root*2);
		level[root] = v[c++];
		get_level(root*2+1);
	}
}
int main()
{
	scanf("%d", &n);
	v.resize(n);
	level.resize(n+1);
	for(int i=0; i<n; i++){
		scanf("%d", &v[i]);
	}
	sort(v.begin() ,v.end());
	get_level(1);
	for(int i=1; i<=n; i++){
		if(i!=1) printf(" ");
		printf("%d", level[i]);
	}
	return 0;
}