题目：

一个学校里老师要将班上N个同学排成一列，同学被编号为 1～N1～N ，他采取如下的方法：

先将 1 号同学安排进队列，这时队列中只有他一个人；

1.2−N 号同学依次入列，编号为i的同学入列方式为：老师指定编号为i的同学站在编号为 1-(i -1) 中某位同学（即之前已经入列的同学）的左边或右边；

2.从队列中去掉 M(M < N) 个同学，其他同学位置顺序不变。

在所有同学按照上述方法队列排列完毕后，老师想知道从左到右所有同学的编号

解题思路：

好多人用链表，但是我觉得树更加容易理解。。。毕竟我这么蒻

d[i].ls表示i点的左儿子，d[i].rs表示i点的右儿子

d[i].v表示当前点是否进入队列

最后输出时按照中序遍历一次输出

Accepted code：

#include
    
     using namespace std;struct node{    int lc,rc,v;}d[101000];void dfs(int x){    if(x==-1)return;    dfs(d[x].lc);//先遍历左儿子    if(d[x].v==0)printf("%d ",x);//如果当前点在队列则输出    dfs(d[x].rc);//再遍历右儿子}int main(){    int n,m; scanf("%d",&n);    d[1].v=0;d[1].lc=d[1].rc=-1;//初始化    for(int i=2;i<=n;i++)    {        int x,y; scanf("%d %d",&x,&y);        d[i].lc=d[i].rc=-1;d[i].v=0;        if(y==0)        {            if(d[x].lc>0)//如果已经有左儿子            {d[i].lc=d[x].lc;d[x].lc=i;}            //有则i的左边是x的左边，x的左边是i            else d[x].lc=i;            //没有则x的左边是i        }        else        {            if(d[x].rc>0)            {d[i].rc=d[x].rc;d[x].rc=i;}             else d[x].rc=i;            //判断右边的同上        }    }    scanf("%d",&m);    for(int i=1;i<=m;i++)        int x;scanf("%d",&x);d[x].v=1;//出队    dfs(1);//中序遍历输出    return 0;}