7-15 完全二叉搜索树 （30 分）_7-5 是否完全二叉搜索树 分数 30

题目描述：

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

输入格式：
首先第一行给出一个正整数 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

分析：

这个题真不会，但是我依然靠着我的混分大法混到了6分。
后来经过学长指点，这个题终于能过了。但是思路却还是不明确。
首先，这是一颗二叉搜索树。那么我首先一定是要将给出的序列进行排序。排序后的序列，就是这颗完全二叉树的中序遍历。
然后，在进行一个非常奇怪的操作。我反正还是不能十分理解。
暂时把AC代码贴上来：

#include"stdio.h"
#include"string.h"
#include"algorithm"
using namespace std;
int a[1001];
int b[1001];
int cnt;
int n;
void dfs(int x)
{
    if(x>n)
        return ;
    dfs(2*x);
    b[x]=++cnt;//对应应该第x号输出对应的第a数组的第cnt元素。
    dfs(2*x+1);
}
int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    dfs(1);
    for(int i=1; i<=n; i++)
        if(i==1)
            printf("%d",a[b[i]]);
        else
            printf(" %d",a[b[i]]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

经过思考加实验， 我发现，这个方法还可以用于给你一个完全二叉树的中序序列，让你求出这颗二叉树的层序序列。