树：前序遍历、中序遍历、后序遍历三者的相互求解_中序遍历和后序遍历

刚刚又 复习 预习了一下树的遍历，也刚好再看看每两种遍历方法组合后建立树的方法；如果能建立一棵完整的树，那也就可以求出另一种遍历序列了。借这个博客刚好记录一下方法，防止以后忘了又得找文章新学一遍

三种遍历的对应的遍历方法：

前序：先遍历根节点，再依次遍历根节点的左子树以及右子树
中序：先遍历左子树，再依次遍历根节点以及其右子树
后序：先遍历根节点的左子树和右子树，最后才是根节点

1、已知前序遍历、中序遍历求后序遍历

解题思想：

前序遍历中，根节点一定是会出现在最前面，我们就可以通过这个点来得到每个子树的根节点；

中序遍历中，一个根节点的左右子树肯定是在根节点的左边和右边，那我们是可以通过这个点来快速得到一棵树的左右子树。

那对于一棵子树，我们可以通过每个节点前序遍历中的位置快速得到其根节点，然后再通过中序遍历，得到其左子树和右子树，这样我们就能更进一步进行后面的遍历了。

上代码吧：

输入(先前序后中序)

6
1 2 3 4 5 6
3 2 4 1 6 5

代码

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
int n,px[105],qx[105],zx[105];  //qx存前序遍历排列、zx存中序遍历
//px存每个数字对应在前序遍历中的位置 
int hx[105],cnt;   //hx存后序遍历排列，cnt记录当前存到的位置 
void ss(int l,int r)
{
    if(l==r)   //只剩一个节点
    {
        //如果是要存下来，把直接输出改成存对应数组就行
        hx[++cnt]=zx[l]; 
        return;
    }
    int xh=1e5,wz;   //寻找当前子树的根节点 
    for(int i=l;i<=r;i++)
    {
        if(px[zx[i]]<xh)
        {
            xh=px[zx[i]];
            wz=i;
        }
    }
    //后序遍历
    if(wz-1>=l) ss(l,wz-1);  //搜索根节点的左子树（先判断存在） 
    if(wz+1<=r) ss(wz+1,r);  //搜索根节点的右子树（先判断存在）
    hx[++cnt]=zx[wz];  //左右子树找完了，那剩下的根节点也可以加入后序序列中了 
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>qx[i];
        px[qx[i]]=i; 
    }
    for(int i=1;i<=n;i++)
        cin>>zx[i];
    ss(1,n);
    for(int i=1;i<=n;i++)
       cout<<hx[i]<<" "; 
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

得到输出：

2、已知后序遍历、中序遍历求前序遍历

解题思想：

后序遍历中，根节点一定是会出现在最后面，我们就可以通过这个点来得到每个子树的根节点；

中序遍历中，一个根节点的左右子树肯定是在根节点的左边和右边，那我们是可以通过这个点来快速得到一棵树的左右子树。

那这种情况跟上面的那种就很像了，那对于一棵子树，我们可以通过每个节点后序遍历中的位置快速得到其根节点，然后再通过中序遍历，得到其左子树和右子树，这样我们就能更进一步进行后面的遍历了。

直接上代码吧：

输入（先中序后后序）

6
3 2 4 1 6 5
3 4 2 6 5 1

代码

//方法代码跟上面那个差不多的，就不写注释了吧 
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
int n,px[105],hx[105],zx[105];
int qx[105],cnt;
void ss(int l,int r)
{
    if(l==r)
    {
        qx[++cnt]=zx[l];
        return;
    }
    int xh=0,wz;
    for(int i=l;i<=r;i++)
    {
        if(px[zx[i]]>xh)
        {
            xh=px[zx[i]];
            wz=i;
        }
    }
    //前序是先根节点，接着左子树右子树的啦 
    qx[++cnt]=zx[wz];
    if(wz-1>=l) ss(l,wz-1);
    if(wz+1<=r) ss(wz+1,r);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>zx[i];
    for(int i=1;i<=n;i++)
    {
        cin>>hx[i];
        px[hx[i]]=i;
    }
    ss(1,n);
    for(int i=1;i<=n;i++)
       cout<<qx[i]<<" "; 
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

得到输出：

3、已知前序遍历、后序遍历求中序遍历

只有前序遍历和后序遍历无法确定一棵树：

以下两棵树都为前序遍历123，后序遍历321的树，但它们并不相同

补充：已知层序遍历、中序遍历求前序遍历、后序遍历

解题思想：

层序遍历中，节点按照层数的从低到高，从左到右排序，那么一棵子树的根节点一定出现在层序遍历的最前面，那便可以确定出子树中的根节点。

中序遍历中，一个根节点的左右子树肯定是在根节点的左边和右边，那我们是可以通过这个点来快速得到一棵树的左右子树。

两者组合，通过层序遍历确定子树根节点，再通过中序遍历分割左右子树，递归下去，即可确定整棵树的形状

上代码：

输入（先层序后中序）

6
1 2 5 3 4 6
3 2 4 1 6 5

代码

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
int n,px[105], cx[105], zx[105];  //zx存中序遍历,px存每个数字对应在前序遍历中的位置 
int qx[105], hx[105], cnt1, cnt2;   //qx存前序遍历排列、hx存后序遍历排列
// cnt1,cnt2记录前序后序当前存到的位置 
void ss(int l,int r)
{
    if(l==r)   //只剩一个节点
    {
        //如果是要存下来，把直接输出改成存对应数组就行
        qx[++cnt1]=zx[l];
        hx[++cnt2]=zx[l]; 
        return;
    }
    int id=1e5,wz;   //寻找当前子树的根节点 
    for(int i=l;i<=r;i++)
    {
        if(px[zx[i]]<id)
        {
            id=px[zx[i]];
            wz=i;
        }
    }
    //向后遍历
    qx[++cnt1]=zx[wz];  //向下遍历前，先将当前根节点加入前序遍历序列 
    if(wz-1>=l) ss(l,wz-1);  //搜索根节点的左子树（先判断存在） 
    if(wz+1<=r) ss(wz+1,r);  //搜索根节点的右子树（先判断存在）
    hx[++cnt2]=zx[wz];  //左右子树找完了，那剩下的根节点也可以加入后序序列中了 
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>cx[i];
        px[cx[i]]=i; 
    }
    for(int i=1;i<=n;i++)
        cin>>zx[i];
    ss(1,n);
    for(int i=1;i<=n;i++)   //输出前序序列
       cout<<qx[i]<<" "; 
    cout << endl;
    for(int i=1;i<=n;i++)  //输出后序序列
       cout<<hx[i]<<" "; 
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

得到输出：