【数据结构】树的遍历：已知后序与中序求前序(先序)序列...

wander

树的遍历：已知后序与中序求前序(先序)序列及代码模板
后序：3, 4, 2, 6, 5, 1（左右根）
中序：3, 2, 4, 1, 6, 5（左根右）

分析：后序序列的最后一位就是树的根节点，在中序序列中找到该根节点，则根节点的左右部分即为左右子树
后序：(3 4 2) (6 5) 1
中序：(3 2 4) 1 (6 5)

找到第一个根节点，接着重复该过程，拆分后序序列的第一部分即左子树
后序：(3 4) 2
中序：(3)2(4)

所以左子树的根节点是 2，其左右孩子为 3 和 4；

右子树同理：
后序：(6) 5
中序：(6) 5
右子树的根节点为5，左孩子为 6；

画出树形结构图：
         1
      /     \
    2        5
  /  \      /
3      4  6
先序序列为 ：(1, 2, 3, 4, 5, 6) (根左右)

那么将上述过程转化为代码：
     因为后序的最后一个总是根结点，令i在中序中找到该根结点，则i把中序分为两部分，左边是左子树，右边是右子树。因为是输出先序（根左右），所以先打印出当前根结点，然后打印左子树，再打印右子树。左子树在后序中的根结点为root – (end – i + 1)，即为当前根结点-右子树的个数。左子树在中序中的起始点start为start，末尾end点为i – 1.右子树的根结点为当前根结点的前一个结点root – 1，右子树的起始点start为i+1，末尾end点为end。

#include<iostream>
using namespace std;

int post[]={3,4,2,6,5,1};
int mid[]={3,2,4,1,6,5};

void pre(int root, int start, int end)              //当前树的根节点  在后序序列中的起始位置  结束位置
{
    if(start>end)
                return ;
    int i=start;
    while(i<end&&mid!=post[root])               //寻找中序序列中根节点的位置
                i++;
    printf("%d ", post[root]);
    pre(root-1-end+i,start,i-1);              //查询左子树
    pre(root-1,i+1,end);                      //查询右子树
}

int main()
{
    pre(5,0,5);
    return 0;
}

————————————————
链接：https://blog.csdn.net/Xylon_/article/details/86613276