前言

• 通常对于一颗树有四种遍历方式，先序遍历，中序遍历，后序遍历，层序遍历，分别对应着：根左右，左根右，左右根，层（类bfs队列实现）

题意

• 存一颗树，输出他的前中后层遍历

思路

• 由题意，给定一个节点的父亲和该节点的左右位置，可以使用一个结构体数组来存储
• 对于前三种遍历方式，使用递归即可实现
• 对于最后一种方式，维护一个队列，pop的同时把该节点的两个儿子加入队列，直到队列为空

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef struct{
    int l,r;
}TREE;
TREE a[505050];
int vis[505050];
void fst(int rt){
    if(rt!=0)printf("%d ",rt);
    if(a[rt].l!=0) fst(a[rt].l);    
    if(a[rt].r!=0) fst(a[rt].r);
}
void mid(int rt){
    if(a[rt].l!=0) mid(a[rt].l);    
    if(rt!=0)printf("%d ",rt);
    if(a[rt].r!=0) mid(a[rt].r);
}
void lst(int rt){
    if(a[rt].l!=0) lst(a[rt].l);    
    if(a[rt].r!=0) lst(a[rt].r);
    if(rt!=0)printf("%d ",rt);
}
void flr(int rt){
    queue<int> b;
    b.push(rt);
    while(!b.empty()){
        printf("%d ",b.front());
        if(a[b.front()].l!=0)b.push(a[b.front()].l);
        if(a[b.front()].r!=0)b.push(a[b.front()].r);
        b.pop();
    }
        
}
int main(){
    int n,u,v,op;
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        scanf("%d%d%d",&u,&v,&op);
        if(op)a[v].r=u;
        else a[v].l=u;
        vis[u]=1;
    }
    int root;
    for(int i=1;i<=n;i++)if(!vis[i])root=i;
    fst(root);
    printf("\n");
    mid(root);
    printf("\n");
    lst(root);
    printf("\n");
    flr(root);
}