1064 Complete Binary Search Tree

题目描述
知识点： 完全二叉树、平衡二叉树
思路： 完全二叉树的性质：除了最后一层非叶子节点外，其余的节点都有左右儿子。并且叶子节点从左往右排列。
完全二叉树存储：使用数组存储，左儿子下标为2*i，右儿子下标为2 * i+1，i/2上取整就是父节点。
1、构造一棵完全二叉树
2、排序序列
3、使用中序遍历遍历二叉树，在遍历的过程中将有序序列填入（二叉搜索树中序一定有序）
4、使用层序遍历输出 对于完全二叉树，层序遍历直接下标从1开始往后访问就是层序了。

#include
#include
using namespace std;
const int N = 1010;
int t[N],res[N],n;
void dfs(int u,int &k){
    if(2*u <= n) dfs(2*u,k);
    res[u] = t[k++];
    if(2*u+1 <= n) dfs(2*u+1,k);
}
int main(){
    cin>>n;
    for(int i = 0;i < n;i++) cin>>t[i];
    sort(t,t+n);
    int k = 0;
    dfs(1,k);
    cout<<res[1];
    for(int i = 2;i <= n;i++) cout<<" "<<res[i];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20