1064 Complete Binary Search Tree (30 分)

题目

题目链接

题解

数据结构。

二叉排序树的中序遍历是单调递增的。

完全二叉树具有很好的顺序存储的性质。

利用中序遍历和递归，先构造左子树，再对根节点进行赋值，再构造右子树。

我是fw。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+10;
int n;
int t[N], a[N], idx;

void build (int x) {
	if (x > n) return ;
	build (x << 1); // left
	t[x] = a[idx ++];
	build (x << 1 | 1); // right
}

int main()
{
	cin >> n;
	for (int i = 0;i < n;i ++) cin >> a[i];
	sort (a, a + n);
	
	build (1);

	for (int i = 1, flag = 0;i <= n;i ++) {
		if (flag) cout << ' ';
		flag = 1;
		cout << t[i];
	}
	return 0;
}