上数据结构讲二叉树时，没有好好听，对知道二叉树的前序和中序求后序或知道中序和后序求前序等问题，可以说是一直不懂，只单单会背：前序（根左右）、中序（左根右）和后序（左右根），口诀是记住了，但是不会灵活运用。

    直到看了一篇博客，网址是：http://www.cr173.com/html/18891_1.html，看完后让我豁然开朗，终于搞懂了。顺便总结下二叉树前序、中序和后序遍历相互求法，即如果只知道两个遍历，如何求第三种遍历方法，比较笨的方法是画出二叉树，然后根据各种遍历不同的特性来求，也可以编程求出，编程求出后面有时间再补上，现在先讲解画二叉树求法。

    首先，我们得清除前序、中序和后序的遍历特性：

    前序遍历（根左右）：

        ①访问根节点

        ②前序遍历左子树

        ③前序遍历右子树

 中序遍历（左根右）：

        ①中序遍历左子树

        ②访问根节点

        ③中序遍历右子树

 后序遍历（左右根）：

        ①后序遍历左子树

        ②后序遍历右子树

        ③访问根节点

一、已知前序、中序遍历，求后序遍历

    例：前序遍历：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;

}

 总结：

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

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