树的遍历关系深入理解（前序，中序，后序互求及分析）

今天做了一个题意思是给定一棵树的前序遍历和中序遍历的结果，求后序遍历的结果。宝宝想了一大会儿，发现还是不会，果断百度一下（好菜是不是）。现把心得写出来分享。
—————————————————————————————————————
先来解决上面的问题，既然是利用树的中序和后序求前序，就兰我们看一下他们之间有什么关系。
前序：根左右 ；中序：左根右 ；后序：左右根。
后序遍历的最后一个必然是根，这样就可以在中序遍历中找到左右子树的范围。

下面举个栗子来说明一下吧

BADCHGEF（中序）
ABCDEFGH （后序）
从后序的最后一个‘H’为当前的根节点，在中序中可看出‘H’左边的是左子树（BADC），右边是右子树（GEF）。由此可以递归左右子树，把左右子树看作一棵新树，重复操作即可 。
下面附上代码

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
char in[100];
char post[100];
int len;
typedef struct A
{
    char c;
    A* l_child;
    A* r_child;
}tree;
tree*   preform(char* in,char* post,int n)
{
    if(n == 0)
    {
        return NULL;
    }
   cout << post[n - 1] ;
   int i = 0;
   for(;i < n;++i)//用来检查左右子树的长度
   {
        if(in[i] == post[n - 1])
        {
            break;
        }
   }
   tree* T = new tree;
    T-> l_child = preform(in,post,i);
    T -> r_child = preform(in + i + 1,post + i,n - i - 1);
    return T;
}
int main()
{
    int a;
    cin >> a;
    while(a--)
    {
        scanf("%s%s",in,post);
         len = strlen(in);
        preform(in,post,len);
        cout << endl;
        memset(in,0,sizeof(in));
        memset(post,0,sizeof(post));
    }
}

如果想由前序和中序求后序原理也是一样的，不再赘述，直接上代码

tree* f(char* pre,char* in,int n)
{
    if(n == 0)
    {
        return NULL;
    }
    tree* T = new tree;
    T -> c = pre[0];
    int i = 0;
    for(;i <= n-1;++i)
    {
        if(pre[0] == in[i])
            break;
    }
    T -> l_child  = f(pre + 1,in,i);
    T -> r_child  = f(pre + i + 1 ,in + i + 1,n - i - 1);
    return T;
}

爱思考的宝宝们可能回想由前序和后序能不能确定一棵树的结构，现在让我们来分析一下确定一棵树的结构需要什么吧，树由左子树，右子树构成，只要确定了这三者一棵树的结构就确定了
上述的两种做法都需要中序遍历的结果，是因为中序可以确切的知道一棵树的左右子树及根
接下来我们分析如果知道前序，后序，看看能不能找到根，左子树，右子树，就行了。
前序是根在前，后序是根在后，仅仅通过这个无法确切的知道左右子树的范围，故不行。
但是知道如果树的度为0或2,也可以确定，但这个是比较特殊的情况，就不详细介绍了。

总结：确定一棵树的结构就是把树进行根，左右子树的划分。