前言：

由于开始做一道DP题需要树形DP的知识点，于是就去学树形DP，但是学树形DP的时候需要用到树的知识点，然后就去学树，学树的重建的时候发现自己不会三种遍历，然后就去学三种遍历QAQ，然后花了一个上午看懂了……（果然没人讲效率低啊QAQ）

二叉树遍历

前序遍历：

1
2
3
4
5
6
7
void First_traversal(int p)
{
    if(p==0) return;
    cout<<a[i].now;
    First_traversal(a[i].leftchild);
    First_traversal(a[i].rightchild);
}

中序遍历：

1
2
3
4
5
6
7
void Second_traversal(int p)
{
    if(p==0) return;
    First_traversal(a[i].leftchild);
    cout<<a[i].now;
    First_traversal(a[i].rightchild);
}

后序遍历：

1
2
3
4
5
6
7
void Third_traversal(int p)
{
    if(p==0) return;
    First_traversal(a[i].leftchild);
    First_traversal(a[i].rightchild);
    cout<<a[i].now;
}

两序求第三序遍历

遍历总结

然后就是二叉树的另一个种求遍历的方法了，个人感觉这方面还是比较难的一点，主要是思想都是理解的，但是代码并不理解，好在想了很久想通了QAQ

首先在遍历二叉树的时候需要知道另外两种遍历方式，现在只支持两种方式，前序+中序→后序和后序+中序→前序；

也就是说我们在遍历二叉树的时候是必须知道中序遍历的，因为中序遍历可以确定当某一个节点只有一个子节点的时候，这个子节点是自己的左儿子还是右儿子，如果没有中序遍历，那么就没办法确定，所以有多种情况出现。

然后具体遍历的思路这里也不在给出，可以参看两个链接，非常详细！

求后序遍历：点击这里

求前序遍历：点击这里

下面的东西注重的是代码实现和代码解释。

前序+中序→后序

注意：la表示中序遍历的开始点（初始值：1），lb为前序（初始值：1）/后序的开始点（初始值：n）

代码：

1
2
3
4
5
6
7
8
9
10
11
void tree(int n,int la,int lb)
{
    if(n<=0) return;
    for(int i=la;i<=la+n-1;i++)
    if(a[i]==b[lb])
    {
        tree(i-la,la,lb+1);
        tree(la+n-i-1,i+1,lb+i-la+1);
        cout<<b[lb];
    }
}

解释：

这个代码其实理解的难点就是在右节点去遍历的时候，长度，前序起点和后序起点的数据得到。其中 la+n-i-1 是右节点的长度计算中，首先是 la+n-1 计算出来的是这个序列（即根节点加他的后辈们的这一个串）在中序遍历中的尾坐标，然后减去根节点的坐标i，剩下的长度就是右边的后辈们的长度。

然后就是起点 i+1 不难理解，i+1 就是根节点i的右边的第一个（起点）。

最后就是 lb+i-la+1 这个计算中，求出来的前序起点其实就是将根节点的坐标加上左边后辈们的长度就是右边后辈们的开始。 i-la+1 就是根节点减去开始节点就是左后辈们加上根节点的长度。

后序+中序→前序

代码：

1
2
3
4
5
6
7
8
9
10
11
void tree_second(int n,int la,int lb)
{
    if(n<=0) return;
    for(int i=la;i<=la+n-1;i++)
    if(a[i]==b[lb])
    {
        cout<<b[lb];
        tree_second(i-la,la,lb-n-la+i);
        tree_second(la+n-i-1,i+1,lb-1);
    }
}

解释：

这里的代码和书上的不是太一样，书上的必须调用前序+中序→后序的代码才能运行，需要写两个函数，比较麻烦于是改进了一下QAQ，其中i-la是长度，然后求左后辈们的时候，后序遍历的开始点为lb-n-la+i，其实就是通过n+la-i计算出来右后辈们的长度，然后用lb减去右后辈们的长度就是左后辈的最后一个点，也就是和根节点接着的一个点。然后求右边的后辈们的时候长度就是总长度减去当前节点i的值，代码要仔细理解，多想想。然后背下来，敲的熟熟的就可以了QAQ；

二叉树重建

前序+中序→重建

1
2
3
4
5
6
7
8
9
10
11
12
13
int Build_Frist_to_Second(int n,int la,int lb)
{
    if(n<=0) return 0;
    for(int i=la;i<=la+n-1;i++)
    if(a[i]==b[lb])
    {
        int This=++now;
        tree[This].ID=a[i];
        tree[This].leftchild=Build_Frist_to_Second(i-la,la,lb+1);
        tree[This].rightchild=Build_Frist_to_Second(la+n-i-1,i+1,lb+i-la+1);
        return This;
    }
}

后序+中序→重建

1
2
3
4
5
6
7
8
9
10
11
12
13
int Build_Frist_to_Second(int n,int la,int lb)
{
    if(n<=0) return 0;
    for(int i=la;i<=la+n-1;i++)
    if(a[i]==b[lb])
    {
        int This=++now;
        tree[This].ID=a[i];
        tree[This].leftchild=Build_Frist_to_Second(i-la,la,lb+1);
        tree[This].rightchild=Build_Frist_to_Second(la+n-i-1,i+1,lb+i-la+1);
        return This;
    }
}

写在最后

二叉树的板子已经总结过了，以后要多敲几遍，争取全部练熟……