虚空终端 • 29天前
思路很抽象,按照结构体存储,因为先序遍历,所以输入建树后存下每个点的深度。
对于查询,倒序遍历深度大小,寻找深度等于目标深度的所有点,因为输入是先序的,所以易证遍历得到的顺序恰好等于该层遍历结果。
理论上层序遍历可以通过这种方式逃过队列。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
struct node
{
int fa,ch[2],value,deep;
};
int maxdep=0;
int idx;
node tree[N];
int input(int fa,int dep)
{
int x;
cin>>x;
if(x==-1)
return 0;
int u=++idx;
tree[u].fa=fa;
maxdep=max(maxdep,dep);
tree[u].deep=dep;
tree[u].value=x;
tree[u].ch[0]=input(u,dep+1);
tree[u].ch[1]=input(u,dep+1);
return u;
}
int main()
{
int root=input(0,1);
for(int i=maxdep;i>=1;i--)
{
for(int j=1;j<=idx;j++)
{
if(tree[j].deep==i)
cout<<tree[j].value<<' ';
}
cout<<endl;
}
return 0;
}
评论:
请先登录,才能进行评论