建树遍历法

想遍历，先建树！

树可以用结构体来存，一个左大儿，一个右大儿

struct node{    int l, r;} Tree[N];

而且只有满足以下两种情况才能建树

①知道前序和中序

例题：https://vjudge.net/problem/HRBUST-2040

看这个样例 首先找到根树的根节点（前序遍历第一个）为 1，然后看中序遍历，得知其左子树的中序遍历为 4 2 5，前序遍历为 2 4 5，右子树的中序遍历为6 3 7，前序遍历为3 6 7，然后递归，将他的左子树变为根树，如此循环

int build(int l1, int r1, int l2, int r2){    //l1 r1是中序遍历的边界，l2 r2是前序遍历的边界    if (l1 > r1) //非法情况        return 0;    int root = pre[l2]; //前序遍历的第一个值位根节点    int p1 = l1;    while (in[p1] != root) //遍历中序遍历找根节点位置          p1;    int p2 = p1 - l1   l2; //将根树分为左儿子和右儿子    Tree[root].l = build(l1, p1 - 1, l2   1, p2);    Tree[root].r = build(p1   1, r1, p2   1, r2);    return root;}

②知道后序和中序

例题：https://pintia.cn/problem-sets/994805046380707840/problems/994805069361299456

将根节点变为后序遍历的最后一个，其他不变即可~

int build(int l1, int r1, int l2, int r2){    //l1 r1是中序遍历的边界，l2 r2是后序遍历的边界    if (l1 > r1) //非法情况        return 0;    int root = pos[r2]; //后序遍历的最后一个值为根节点    int p1 = l1;    while (in[p1] != root) //遍历中序遍历找根节点位置          p1;    int p2 = p1 - l1   l2; //将根树分为左儿子和右儿子    Tree[root].l = build(l1, p1 - 1, l2, p2 - 1);    Tree[root].r = build(p1   1, r1, p2, r2 - 1);    return root;}

可以看出两种情况基本上没啥区别，最后输出就行了

①前序遍历 根左右

void getpos(int x){    printf("%d ", x);    if (Tree[x].l != 0)        getpos(Tree[x].l);    if (Tree[x].r != 0)        getpos(Tree[x].r);}

②中序遍历 左根右

void getpos(int x){    if (Tree[x].l != 0)        getpos(Tree[x].l);    printf("%d ", x);    if (Tree[x].r != 0)        getpos(Tree[x].r);}

③后序遍历 左右根

void getpos(int x){    if (Tree[x].l != 0)        getpos(Tree[x].l);    if (Tree[x].r != 0)        getpos(Tree[x].r);    printf("%d ", x);}

这仨没啥区别，就是输出位置不一样
④层次遍历 bfs

void bfs(int x){    queue<int> q;    q.push(x);    while (q.size())    {        int t = q.front();        q.pop();        if (Tree[t].l != 0)            q.push(Tree[t].l);        if (Tree[t].r != 0)            q.push(Tree[t].r);        if (t != x)            printf(" ");        printf("%d", t);    }}

可能之后还会补充？ ε=(´ο｀*)))唉 tnl