1064 Complete Binary Search Tree (30分)

主要是一开始没弄清题目中完全二叉树的定义

思路：

一棵排序二叉树的中序遍历就是这一组数的递增序列。这边是完全二叉树，假设从0开始，那么节点i的左孩子的标号就是2i+1，右孩子的标号就是2(i+1)。先将这组数按照递增来排序，然后用中序遍历复原这棵完全排序二叉树，最后直接输出。

完全二叉树：任何一个节点编号x，则左孩子节点为2x，右孩子节点为2x+1
可以使用一个数组存储，从1到n
结论：该数组中元素存放的顺序为该二叉树的层序遍历序列

利用完全二叉树建立结构，中序遍历填入元素

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000 + 10;

int a[maxn], ans[maxn], cnt, N, i;
void in_order(int root) {
	if (root > N)
		return;
	in_order(root * 2);
	ans[root] = a[cnt++];
	in_order(root * 2 + 1);
}

int main(int argc, char const *argv[])
{
	cin >> N;
	for (i = 0; i < N; ++i)
		cin >> a[i];
	sort(a, a + N);
	cnt = 0;
	in_order(1);
	for (i = 1; i <= N - 1; ++i)
		cout << ans[i] << " ";
	cout << ans[i] << endl;

	return 0;
}