[数据结构与算法]【算法】【树】已知先序中序序列求后序序列（详细解释）

题目描述

如题所示，已知先序中序序列建树与求后序序列

算法原理

????????利用递归和分制的思想，找到当前树先序序列的根节点，然后找到对应中序序列的位置，然后根据根节点在中序序列中的位置来判断左右子树分别的位置，然后继续对左右子树进行递归，最后得出结果

post(0, 0, 序列总长度-1);

void post(int root, int start, int end)

?????????首先是递归函数进入，其中三个形参分别代表的含义为

? ? ? ????????? root? ? ? ? 先序序列中当前递归层中根节点的下标

? ? ? ????????? start? ? ? ? 中序序列中子树的最左下标（子树开始的下标）

? ? ? ????????? end? ? ? ? 中序序列中子树的最右下标（子树结束的下标）

if(start > end)     return ;

?????????递归结束的标志，因为子树的元素范围在下标[start,end]之内，当start>end的时候，说明以当前节点为空节点

int i = start;

? ? ? ? 这里的i相当于只在中序遍历中有效，这里的i对于查找根节点root的先序序列完全没有意义，仅代表root在中序序列中的下标位置

例子：

?假设一棵二叉树为上面的形式，那么他的先序序列和中序序列为

递归原理：

? ? ? ? 重点要解释一下这里的两条递归语句，分别代表递归当前根节点的左子树和当前根节点的右子树

????????对于左子树

post(root + 1, start, i - 1);    //递归左子树

???????如图可见，当遍历左子树的时候，

???????对于先序序列，左子树的根节点为先序序列上一层根节点root的下一个节点，也就是root+1

???????对于中序序列，因为是左子树，所以启始start值不变，end应该为在中序序列中找到的根节点i的前一个节点也就是i-1

????????对于右子树

post(root + 1 + i - start, i + 1, end);

中序序列中的启始位置和结束位置都比较好确定，启始位置为i+1，结束位置为end

????????主要的难点就在于root的确认，我们能知道在先序序列中，是按照根节点——左子树——右子树排列的，左子树的根节点在先序序列中就为本层的根节点+1（root+1），比较好确定，但是右子树的跟节点就没有那么好确认了，但是我们细想就可以知道，原本的根节点加上左子树的节点个数，那不就到了右子树了嘛，但是这个想法也不准确

????????首先左子树的节点个数可以根据中序序列来判断，为i-start，但是根节点加上左子树的节点总数（root+（i-start））仅仅代表了左子树的最右侧节点，再加1才能代表右子树的第一个端点

? ? ? ? 有这幅图就可以比较清楚的看出

? ? ? ? 那么就引出了另一个问题了为什么根节点不能直接是i+1，而是要绕这么大一个圈子回来呢？

? ? ? ? 这就需要下一步递归来判断了?

?这样就比较容易能看出来了，正确的根节点应该是6

但是i+1仅仅表示7，明显与答案不符

实际上i仅仅在中序序列中有意义，放在先序序列中并没有什么意义

核心代码实现

参考柳婼已知前序（先序）与中序输出后序_柳婼 の blog-CSDN博客

#include <cstdio>
using namespace std;
int pre[] = {1,2,3,4,5,6,7,8};
int in[] = {4,3,5,2,7,6,8,1};
void post(int root, int start, int end) {
    //root? ? ? ? 先序序列中当前递归层中根节点的下标
    //start? ? ? ? 中序序列中子树的最左下标（子树开始的下标）
    //end? ? ? ? 中序序列中子树的最右下标（子树结束的下标）
    if(start > end)     return ;    /*递归结束的标志，因为子树的元素范围在下标[start,end]之内，当start>end的时候，说明以当前节点为空节点*/
    int i = start;    //这里的i对于查找根节点root的先序序列完全没有意义，仅代表root在中序序列中的下标位置
    while(i < end && in[i] != pre[root]) i++;    //寻找root在中序序列中的位置
    post(root + 1, start, i - 1);                //递归左子树
    post(root + 1 + i - start, i + 1, end);        //递归右子树
    printf("%d ", pre[root]);                    //输出后序序列
}
 
int main() {
    post(0, 0, 7);
    //这里的总长度是pre.size()-1,而不是pre.size()
    return 0;
}

例题