二叉树前序、中序和后序遍历相互求法

    上数据结构讲二叉树时，没有好好听，对知道二叉树的前序和中序求后序或知道中序和后序求前序等问题，可以说是一直不懂，只单单会背：前序（根左右）、中序（左根右）和后序（左右根），口诀是记住了，但是不会灵活运用。
    直到看了一篇博客，网址是：，看完后让我豁然开朗，终于搞懂了。顺便总结下二叉树前序、中序和后序遍历相互求法，即如果只知道两个遍历，如何求第三种遍历方法，比较笨的方法是画出二叉树，然后根据各种遍历不同的特性来求，也可以编程求出，编程求出后面有时间再补上，现在先讲解画二叉树求法。
    首先，我们得清除前序、中序和后序的遍历特性：
    前序遍历（根左右）：
        ①访问根节点
        ②前序遍历左子树
        ③前序遍历右子树
    中序遍历（左根右）：
        ①中序遍历左子树
        ②访问根节点
        ③中序遍历右子树
    后序遍历（左右根）：
        ①后序遍历左子树
        ②后序遍历右子树
        ③访问根节点
        
一、已知前序、中序遍历，求后序遍历
    例：前序遍历：GDAFEMHZ   中序遍历：ADEFGHMZ
    画树求法：
        第1步：根据前序遍历的特点，我们可以知道根节点为G。
        第2步：根据中序遍历ADEFGHMZ，根据“左根右”遍历规则，其中根节点G左侧的ADEF必然是根的左子树，G右侧的HMZ必然是根的右子树。
        第3步：观察左子树ADEF，左子树中的根节点必然是大树根节点G的左孩子；在前序遍历中，大树的根节点G的左孩子位于根节点G之后，所以左子树的根节点为D。
        第4步：同理可得根节点G的右子树节点HMZ的根节点也可以通过前序遍历求得。在前序遍历中，一定是先把根节点G和根节点G的所有左子树节点遍历完之后才会遍历右子树，并且遍历的左子树的第一个节点就是左子树的根节点；同理，遍历的右子树的第一个节点就是右子树的根节点。
        第5步：观察发现，上面的过程是递归的。先根据前序找到当前树的根节点，然后根据中序划分左子树，右子树，然后进入左子树重复上面的过程，然后进入右子树重复上面的过程。最后就可以还原一棵树了。递归的过程可以简洁表达为：
        ①确定根，确定左子树，确定右子树
        ②在左子树中递归
        ③在右子树中递归
        ④打印根
    那么，可以画出这个二叉树的形状为：
        
    那么，根据后序的遍历规则“左右根”，可以知道，后序遍历顺序为：AEFDHZMG

    编程求法：（根据上面的思路，写递归程序）
    

#include <iostream>
#include <string>

using namespace std;

struct node//二叉树结点
{
    struct node *left;//左孩子
    struct node *right;//右孩子
    char data;//当前结点的值
};

void binaryTreeOrdering(char *pr,char *in,int len)
{
    if(0 == len)//递归返回条件
    {
        return;
    }
    struct node *curNode = new struct node;//创建新结点
    curNode->data = *pr;//保存当前前序遍历中的根结点
    int rootIndex = 0;//当前根结点的下标
    for(;rootIndex < len;rootIndex++)//遍历当前中序遍历，求出当前根结点的下标
    {
        if(in[rootIndex] == curNode->data)
            break;
    }
    //递归查看当前根结点是否还有左孩子
    binaryTreeOrdering(pr+1,in,rootIndex);
    //递归查看当前根结点是否还有右孩子
    binaryTreeOrdering(pr+rootIndex+1,in+rootIndex+1,len-(rootIndex+1));
    cout<<curNode->data;//输出当前根结点
    //注：其实就是“左右根”的编程思想
    return;
}

int main(int argc, const char *argv[])
{
    char *pr = "GDAFEMHZ";//前序遍历
    char *in = "ADEFGHMZ";//中序遍历
    //递归输出后序遍历
    binaryTreeOrdering(pr,in,8);
    cout<<endl;
    return 0;
}

二、已知中序和后序遍历，求前序遍历
    依然是上面的题，这次给出中序和后序遍历：
    中序遍历：ADEFGHMZ    后序遍历：AEFDHZMG
    画树求法：
    第1步：根据后序遍历的特点，我们知道后序遍历最后一个节点即为根节点，即为根节点G。
    第2步：根据中序遍历ADEFGHMZ，根据“左根右”遍历规则，其中根节点G左侧的ADEF必然是根的左子树，G右侧的HMZ必然是根的右子树。
    第3步：观察中序左子树ADEF，中序左子树中的根节点必然是大树根节点G的左孩子；在后序遍历“左右根”规则中，最后为根节点，大树的根节点G的左孩子为后序左子树AEFD中的D节点，所以左子树的根节点为D。
    第4步：同理可得根节点G的右子树节点HMZ的根节点也可以通过后序遍历求得。在后序遍历中，一定是先把根节点G的所有左子树节点遍历完之后再遍历右子树，最后遍历根节点G，并且遍历的左子树的最后一个节点就是左子树的根节点；同理，遍历的右子树的最后一个节点就是右子树的根节点。
    第5步：观察发现，上面的过程是递归的。先根据前序找到当前树的根节点，然后根据中序划分左子树，右子树，然后进入左子树重复上面的过程，然后进入右子树重复上面的过程。最后就可以还原一棵树了。
    那么前序遍历为：GDAFEMHZ。
    
    编程求法：（根据上面的思路，写递归程序）
    

#include <iostream>
#include <string>

using namespace std;

struct node//二叉树结点
{
    struct node *left;//左孩子
    struct node *right;//右孩子
    char data;//当前结点的值
};

void binaryTreeOrdering(char *af,char *in,int len)
{
    if(0 == len)//递归返回条件
    {
        return;
    }
    struct node *curNode = new struct node;//创建新结点
    curNode->data = *(af+len-1);//保存当前后序遍历中的根结点
    cout<<curNode->data;//输出当前根结点
    int rootIndex = 0;//当前根结点的下标
    for(;rootIndex < len;rootIndex++)//遍历当前中序遍历，求出当前根结点的下标
    {
        if(in[rootIndex] == curNode->data)
            break;
    }
    //递归查看当前根结点是否还有左孩子
    binaryTreeOrdering(af,in,rootIndex);
    //递归查看当前根结点是否还有右孩子
    binaryTreeOrdering(af+rootIndex,in+rootIndex+1,len-(rootIndex+1));
    //注：其实就是“根左右”的编程思想
    return;
}

int main(int argc, const char *argv[])
{
    char *af = "AEFDHZMG";//后序遍历
    char *in = "ADEFGHMZ";//中序遍历
    //递归输出前序遍历
    binaryTreeOrdering(af,in,8);
    cout<<endl;
    return 0;
}

    总结：
    已知前序和中序求后序：前序遍历可以知道第一个节点为根节点，再根据中序遍历和已知根节点，划分左子树和右子树，根据前序遍历“根左右”规则可知左子树和右子树的第一个节点也为根节点，再根据新的根节点和中序遍历，再次划分左子树和右子树，以此类推（递归），最后还原成一棵树。
    已知中序和后序求前序：后序遍历可以知道最后一个节点为根节点，再根据中序遍历和已知根节点，划分左子树和右子树，根据后序遍历“左右根”规则可知左子树和右子树的最后一个节点为根节点，再根据新的根节点和中序遍历，再次划分左子树和右子树，以此类推（递归），最后还原成一棵树。