一个无重复的非负整数序列，必定对应唯一的一棵形状为完全二叉树的二叉搜索树。本题就要求你输出这棵树的层序遍历序列。
输入格式：
首先第一行给出一个正整数 N（≤），随后第二行给出 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> using namespace std; int mp[1005],a[1005],cnt,n; void dfs(int x) { if(x>n)return ; dfs(x*2); a[x]=++cnt;//该行的位置变换 也可以由先序后序推出层序 //x表示层序遍历时第x个出现 //cnt 表示中序遍历时的下标 dfs(2*x+1); } int main() { int i;cin>>n; for(i=1;i<=n;i++)cin>>mp[i]; sort(mp+1,mp+1+n); dfs(1); for(i=1;i<=n;i++){ if(i!=1)cout<<" "; cout<<mp[a[i]]; } }
中序（先序后序也可）推层序
上面dfs记录的是中序遍历时的该数 在层序遍历时出现的下标；cnt不断累加表示中序遍历，x表示层序遍历时的下标
下面层序推中序的dfs就直接根据层序的下标，搜出中序遍历时的顺序 然后直接按序输出
#include<bits/stdc++.h> using namespace std; int n,mp[1005]; void dfs(int x) { if(x>n)return; dfs(x*2); printf("%d ",mp[x]); dfs(x*2+1); return; } int main() { int i;cin>>n; for(i=1;i<=n;i++)cin>>mp[i]; dfs(1); return 0; }
层序推中序（完全二叉树情况下
原文链接: https://www.cnblogs.com/ydw--/p/12582230.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/348705
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
