创建一棵完全二叉搜索树

题目大意：给出一组不超过1000个的序列，生成一棵完全二叉搜索树并层序输出

算法思路：

       1、由于是创建一棵完全二叉树，结点从上至下从左至右与数组下标相同，于是建树采用数组形式

       2、对给出的一组无序序列从小到大排序，得到arr[ ]

       3、根据二叉搜索树的性质，某一结点的左子树都小于该结点，右子树都大于该结点，根据完全二叉树的性质，给定一个固定大小的结点总数n，就可以计算出根结点左子树的结点总数x，于是有序序列arr的前x个就是左子树，第x+1就是根结点，剩下的就是右子树。

      4、从根结点开始对数列递归划分，得到完全二叉搜索树T[ ]，顺序输出就得到层序遍历的结果

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 1010;
int arr[maxn],T[maxn];

//获取有n个结点的完全二叉树左子树的个数
int getLeftLength(int n){
    //不包括叶子结点的完美二叉树的高度
	int height = floor(log(n+1)/log(2)); 
    //完全二叉树第height+1层的结点数，也就是叶子节点数   
	int x = n + 1 - pow(2,height); 
    //取min(叶子节点数，叶子节点数的一半)
	x = min(x,(int)pow(2,height-1));
    //返回左子树的结点个数
	return ((int)pow(2,height-1))- 1 + x;
}

//处理arr[ALeft,ARight]序列
//初始调用solve(0,n-1,0)
void solve(int ALeft, int ARight, int TRoot){
    //要处理的结点数n
	int n = ARight - ALeft + 1;
    //递归终止条件
	if(n == 0) return;
    //当前序列中根结点左子树的结点个数
	int L = getLeftLength(n);
    //用来存储完全二叉搜索树的序列数组T，当前序列中根结点的值arr[ALeft + L]
	T[TRoot] = arr[ALeft + L];
    //根据完全二叉树的性质，TRoot的左孩子下标为TRoot*2 + 1 (根结点下标从0开始)
	int LeftTRoot = TRoot*2 + 1;
	int RightTRoot = LeftTRoot + 1;
    //递归处理左子树
	solve(ALeft,ALeft+L-1,LeftTRoot);
    //递归处理右子树
	solve(ALeft+L+1,ARight,RightTRoot);
}

int main(){
	int n;
	scanf("%d",&n);
	for(int i=0; i<n; i++) scanf("%d",&arr[i]);
	sort(arr,arr+n);
	solve(0,n-1,0);
	for(int i=0; i<n; i++){
		if(i) printf(" ");
		printf("%d",T[i]);
	}
	return 0;
}