给你一个整数序列,用这些数构成一个完全二叉排序树,输出此二叉树的层序遍历序列。输入的第一行是一个整数n,表示这个整数序列的长度,输入的第二行包含n个整数,每个数代表完全二叉排序树的一个节点,现在需要输出由这n个整数构成的完全二叉排序树的层序遍历序列。
输入样例
18
56 987 -25 0 1021 -238 399 12 77 -1 72190 -25 -168 -41367 3218 12 0 -25
输出样例
12 -1 987 -25 0 77 3218 -238 -25 0 12 56 399 1021 72190 -41367 -168 -25
思路:对于二叉搜索树而言,它的中序遍历序列是非递减的。因此可以通过排序得到中序序列。
对于本题而言,我们没有必要复现完整的树结构,只需要求出它的层序遍历序列即可。
我们可以构建一棵新的完全二叉树T2,每个节点存储它的层数。
利用中序遍历T2,得到原始完全二叉树每个节点的层,接着按照层输出即可。
‘’‘
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int maxn = 1e4 + 10;
int n,level,idx = 1;
int a[maxn],in[maxn],layer[maxn];
vector[HTML_REMOVED] v[20];
void visits(int root){
if(root > n)
return ;
else{
visits(2 * root);
layer[idx] = in[root];
visits(2 * root + 1);
}
}
int main()
{
cin >> n;
for(int i = 1;i <= n;i) scanf(“%d”,&a[i]);
sort(a + 1,a + 1 + n);
int count = 1,num = 0,idx = 1;
for(int i = 1;num <= n;i++)
{
level++;
for(int k = 0;k < count && num <= n;k++)
{
in[idx++] = i;
num++;
}
count *= 2;
}
visits(1);
for(int i = 1;i <= n;i++)
{
int t = layer[i];
v[t].push_back(a[i]);
}
for(int i = 1;i <= level;i++){
for(int j = 0;j < v[i].size();j++)
cout<<v[i][j]<<" ";
}
return 0;
}
/
12 -1 987 -25 0 77 3218 -238 -25 0 12 56 399 1021 72190 -41367 -168 -25
/
‘’‘