n叉树的先序非递归遍历
#include<stdio.h>#define N1 30000001
#define N2 300001
int a[N2],b[N2],m1[N2],m2[N2];
int t[N1],parent[N1];
int i,j,sum,n,m,te;
int mark()
{
int stk[N2],k,u;
long p;
k=0;p=0;stk[k]=0;u=0;
while(p!=sum*2+1)
{
if(u<n&&a[u]<=b[u])
{
k++;p++;
stk[k]=a[u];
if(stk[k]<n) m1[stk[k]]=p;
else t[stk[k]]=p;
u=a[u];
}
else
{
p++;
if(stk[k]<n) m2[stk[k]]=p;
else t[stk[k]]=p;
k--;
u=parent[u];
a[u]=a[u]+1;
}
}
return 0;
}
int main()
{
int ii,k1,k2,kase;
scanf("%d",&kase);
for (ii=1;ii<=kase;++ii)
{
scanf("%d",&n);
sum=0;
for(i=0;i<n;++i)
{
scanf("%d",&te);
a[i]=sum+1;b[i]=sum+te;
for(j=1;j<=te;j++) parent[j+sum]=i;
sum+=te;
}
mark();
scanf("%d",&m);
printf("Case %d:\n",ii);
for (i=1;i<=m;++i)
{
scanf("%d%d",&k1,&k2);
if (k1==k2) printf("No\n");
else
if (k1>=n)
printf("No\n");
else
if (k2>=n)
if ((m1[k1]<t[k2])&&(t[k2]<m2[k1]))
printf("Yes\n");
else printf("No\n");
else
if((m1[k1]<m1[k2])&&(m2[k1]>m2[k2]))
printf("Yes\n");
else printf("No\n");
}
if (ii<kase) printf("\n");
}
return 0;
}
页:
[1]
