天梯赛练习——Complete Binary Search Tree (30分)

题目：

分析：

本题涉及到 完全二叉树 二叉搜索树，对于给出的数据，只要经过排序之后则一定为二叉搜索树中序遍历的结果，由于题目要求的是构造完全二叉树，所以对于下标为 x 的节点，左孩子一定为 2x ， 右孩子一定为 2x+1，则使用递归建树即可

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 1005;
int num[MAXN],ans[MAXN];
int n,cnt;

void BuildTree(int root)
{
    if(root > n) return;
    BuildTree(2*root);   //利用了完全二叉树的性质
    ans[root] = num[++cnt];
    BuildTree(2*root+1);
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&num[i]);
    sort(num+1,num+n+1);
    BuildTree(1);
    for(int i=1;i<=n;++i)
        if(i == n)
            printf("%d\n",ans[i]);
        else
            printf("%d ",ans[i]);
    return 0;
}