7-13 完全二叉搜索树（树的中序遍历）

题目描述：

一个无重复的非负整数序列，必定对应唯一的一棵形状为完全二叉树的二叉搜索树。本题就要求你输出这棵树的层序遍历序列。

输入格式：

首先第一行给出一个正整数 N（≤1000），随后第二行给出 N 个不重复的非负整数。数字间以空格分隔，所有数字不超过 2000。

输出格式：

在一行中输出这棵树的层序遍历序列。数字间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

10 1 2 3 4 5 6 7 8 9 0

输出样例：

6 3 8 1 5 7 9 0 2 4

参考代码如下，详见注释：

#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define LL long long
using namespace std;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const int N =1e5+2;

int tree[1002]; //数组存储
int ans[1002]; //存储层序遍历结果，i节点在原数组的位置
int cnt; //下标 
int n; //n个整数

/*
完全二叉搜索树 
完全(叶子结点只能出现在最下层和次下层) 
搜索树(根节点的所有左子树值小于根节点，所有右子树值大于根节点) 
*/
//左根右，中序遍历，从底自上更新。 
void solve(int x)
{
	if(x>n)return; //超出返回
	solve(2*x); //根节点左子树
	ans[x]=cnt++; //原数组下标 
	solve(2*x+1);//根节点右子树 
}
int main()
{
	IO;
 	cin>>n;
 	for(int i=1;i<=n;++i)
 	{
 		cin>>tree[i];
	 }
	 //从小到大排序数组，这样该数组就是完全二叉搜索的中序遍历了 
	 sort(tree+1,tree+1+n);
     //下标从1开始
	 cnt=1;
	 solve(1);
	for(int i=1;i<=n;++i)
	{
		if(i!=1)cout<<" ";
		cout<<tree[ans[i]];
	 } 
	return 0;
}