[PAT解题报告] Complete Binary Search Tree
给定一些整数值，构造一个完全排序二叉树。
完全的定义是，几乎是满的二叉树，但是最后一层可能从右往左按顺序少了一些叶子节点。
其实这个题也不难。中序遍历排序二叉树，得到值的顺序是排好顺序的。我们用编号为1的节点为根，编号x的节点左孩子是2 ＊ x,
右孩子是2 * x +
1。完全的意思是说，编号是连续出现的，恰好是1-n，我们从1开始左中序遍历，维护编号就可以了，编号>n的不用就可以了。
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
int a[1024],b[1024],n;
void dfs(int node,int &ind) {
if (node > n) {
return;
}
dfs(node << 1, ind);
a[node] = b[ind++];
dfs((node << 1) | 1, ind);
}
int main() {
scanf("%d",&n);
for (int i = 0; i < n; ++i) {
scanf("%d",b + i);
}
sort(b, b + n);
int x = 0;
dfs(1, x);
for (int i = 1; i <= n; ++i) {
if (i > 1) {
putchar(' ');
}
printf("%d",a[i]);
}
puts("");
return 0;
}
原题链接：http://www.patest.cn/contests/pat-a-practise/1064
