|
在二叉树这种数据结构中，有三种遍历方式，分别是前序（也叫先序）遍历，中序遍历，和后序遍历。当然有的地方还会有按层遍历。
前序遍历：根->左->右
中序遍历：左->根->右
后序遍历：左->右->根
按层遍历：从第一层开始一直到最后一层，类似按着完全二叉树的编号一个一个输出
先说上面前三种遍历的相互转换， 当已知前序遍历序列和中序遍历序列的时候，可以确定它的后序遍历序列。 当已知后序遍历序列和中序遍历序列的时候，可以确定它的前序遍历序列。 但是当已知前序遍历序列和后序遍历序列的时候，它的中序遍历序列不一定 就不唯一，也就是说已知前序和后序不一定能推出中序。 下面会详细讲解已知前序和中序或者已知后序和中序来求另一种序列的思路还代码。
1.已知后序和中序序列求前序序列。
举个栗子，比如说后序序列是3，4，2，6，5，1（左右根）中序序列是3，2，4，1，6，5（左根右） 思路：后序序列的最后一个数字（1）必定为整棵二叉树的根节点，然后在中序序列中找到1的位置可以确定这个根节点的左右子树分别是多少，（此时1的左子树为3 2 4 ，右子数为6 5）然后将3 2 4这颗树在后序序列中寻找可以找到它的左子树的根节点为2，6 5 这颗右子树的根为5以此类推，可以找到所有点。最后得到前序序列：1 2 3 4 5 6 ； 代码如下：
#include
using namespace std;
int post[]={3,4,2,6,5,1};
int in[]={3,2,4,1,6,5};
void pre(int root,int start,int end)
{
if(start>end) return ; //退出条件，这棵树的范围为0
int i=start;
while(iends) return;
int i=start;
while(i |