PAT-A1064，题目地址：https://www.patest.cn/contests/pat-a-practise/1064
对搜索树的中序遍历就是对数的排序；
将1作为complete二叉树的root，则每个节点的子节点都是父节点的的下标的2倍或者2倍+1；
思路：
- 对数组进行从小到大排序
- 对tree进行中序遍历，记录中序遍历的下标的顺序（以示例为例：8，4，9，2，10，5，1，6，3，7，注意根节点的下标为1假设）
- 还原树，将树存在数组中，则依次输出就是层序遍历的结果（6 3 8 1 5 7 9 0 2 4）
代码如下：
#include <cstdio>
#include <algorithm>
int main(){
int count;
int num[1002], res[1002];
scanf("%d", &count);
for(int i = 0; i < count; i++){
scanf("%d", &num[i]);
}
std::sort(num, num + count);
int first = 1; //first是中序遍历过程中第一个要访问的节点的下标
while(first * 2 <= count){
first *= 2;
}
int now = first, index = 0; // now代表中序遍历过程中正在访问的节点的下标
while(1){ //进行中序遍历
res[now] = num[index++];
if(2 * now + 1 <= count){
now = 2 * now + 1;
while(2 * now <= count){
now *= 2;
}
}
else if(now % 2 == 0){
now /= 2;
}
else{
while(now % 2 == 1){
now /= 2;
}
now /= 2;
}
if(now == 0){
break;
}
}
//以下为结果输出
for(int i = 1; i <= count; i++){
if(i > 1){
printf(" ");
}
printf("%d", res[i]);
}
printf("\n");
return 0;
}
