先序 中序 后序
首先，我们看看前序、中序、后序遍历的特性：
前序遍历：
1、访问根节点
2、前序遍历左子树
3、前序遍历右子树
（个人觉得这个命名略微有误导性，因为前序的“前”容易让人误会成树的最前边（视觉上的左边）。记住前序遍历就是最直接（直觉上的）遍历，中左右）
中序遍历：
1、中序遍历左子树
2、访问根节点
3、中序遍历右子树
（同样是有误导性的名字。遍历顺序，左中右）
后序遍历：
1、后序遍历左子树
2、后序遍历右子树
3、访问根节点
（同样是有误导性的名字，“后”字没有任何意义，所有二叉树的遍历，左边一定在右边的之前进行遍历。遍历顺序，左右中。）
最近又想出一个帮助记忆的方法，把先、中、后当做是“中”的访问时序。如先序就是“中”排在最前面（中左右），以此类推。
接着，铭记总的方针
1、到根节点，确定左子树，确定右子树（最重要）
2、对左子树进行递归分析
3、对右子树进行递归分析
一、已知先序、中序遍历，求后序遍历
例：
先序遍历:
GDAFEMHZ
中序遍历:
ADEFGHMZ
思路分析：
1、根据先序遍历的特点，中左右，第一个元素一定是根节点，所以立刻确定G是根节点。
2、既然确定了G是根节点，再根据中序遍历的特点，左中右，在根节点G之前的ADEF就是左子树，根节点G之后的HMZ就是右子树。
3、接着分析左子树（思路和第1，2步一样）。把左子树的所有元素（即ADEF这四个元素）在先序遍历和中序遍历中的顺序拿出来进行比较。
先序的顺序是DAFE（中左右），中序遍历是ADEF（左中右）。
通过先序特点得出D是左子树的节点，通过中序特点确定唯一一个在D左边的A是左子树中的左叶子，右边的是EF。
观察EF的相对位置，在先序（中左右）是FE，在中序（左中右）EF，所以得出EF的关系是左中。
到此得出左子树的形状
4、接着分析右子树（思路和第1，2步一样），把右子树的元素（HMZ）在先序遍历和中序遍历中的顺序拿出来进行比较。
先序中序后序遍历二叉树
先序的顺序是MHZ（中左右），中序遍历是HMZ（左中右）。
根据先序遍历的特点确定M是右子树的节点，根据中序遍历的特点确定H是左叶，Z是右叶。
所以右子树的形状
5、于是得出了整棵树的形状
那么后序遍历就是AEFDHZMG
二、已知中序和后序遍历，求前序遍历
中序遍历:
ADEFGHMZ
后序遍历:
AEFDHZMG
思路分析：（记住方针是一样的）
1、根据后序遍历的特点（左右中），根节点在结尾，确定G是根节点。根据中序遍历的特点（左中右），确定ADEF组成左子树，HMZ组成右子树。
2、分析左子树。ADEF这四个元素在后序遍历（左右中）中的顺序是AEFD，在中序遍历（左中右）中的顺序是ADEF。根据后序遍历（左右中）的特点确定D是左子树的节点，根据中序遍历（左中右）的特点发现A在D前面，所以A是左子树的左叶子，EF则是左子树的右分枝。
EF在后序（左右中）和中序（左中右）的相对位置是一样的，所以EF关系是左右或者左中，排除左右关系（缺乏节点），所以EF关系是左中。
到此得出左子树的形状
3、分析右子树。HMZ这三个元素在中序遍历（左中右）的顺序是HMZ，在后序遍历（左右中）的顺序是HZM。根据后序遍历（左右中）的特点，M在尾部，即M是右子树的节点。再根据中序遍历（左中右）的特点，确定H（M的前面）是右子树的左叶子，Z（M的后面）是右子树的右叶子。
所以右子树的形状
4、最后得出整棵树的形状
那么先序遍历就是GDAFEMHZ。
三、已知前序、后序遍历，求中序遍历
这种情况，可能无法还原出唯一的二叉树，因为无法唯一确定根节点的左右子树。
（其实还不大清楚具体的证明和原因，欢迎指教）

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。