7-1 根据后序和中序遍历输出先序遍历 (PTA-数据结构)_本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果,输出该树的前序遍历结果

本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果，输出该树的先序遍历结果。

输入格式:

第一行给出正整数N(≤30)，是树中结点的个数。随后两行，每行给出N个整数，分别对应后序遍历和中序遍历结果，数字间以空格分隔。题目保证输入正确对应一棵二叉树。

输出格式:

在一行中输出Preorder: 以及该树的先序遍历结果。数字间有1个空格，行末不得有多余空格。

输入样例:

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例:

Preorder: 4 1 3 2 6 5 7

通过截图：

 

---

 思路分析：

        起初看到后序遍历和中序遍历，第一想法是用这个数组创建一棵树，但是考虑到我之前写过的创建树的代码不接受这样的输入（以前的问题），因此开始考虑能不能通过我们人类的思维方式，来想一个能用后序和中序推出先序的算法（相信三者转换是有规律的，因为我们做那种简答题或者选择题，也是按照一定规律推到树，然后写出来的）。

        例如：

---

       要知道，后序（Post）遍历是LRV，中序（Min）遍历是LVR，先序（Pre）遍历是VLR（V 根节点，L 左子树结点，R 右子树结点）。下面写一下该题的图示：

        其中，我们不难发现， Post的最后一个字符是根节点（Post的最后一个，Pre的第一个），该结点下面的左子树的根节点是第二个我们要输出的，以此类推。

人类手绘创建的树如下：

        我们在手绘树的时候，发现，在中序遍历数组中所找到根节点，左边的是左子树，右边的是右子树，即  (1((2)3))4((5)6(7)) 红色括号为右子树，深绿为左子树，准备好之后，明白我们要找到根（root），子树一个括号中的第一个元素位置（start），子树括号最后一个元素位置（fin）。

        树大概是比较推荐用递归来写，所以我选择了用递归来写，之后疯狂debug折磨自己。因为非递归的思路不是很清楚，我们下面决定用递归来写（之前文章内容就没写过非递归的遍历检查，所以这里行进困难），递归的思路是先序遍历寻找，找到本次操作的根节点后，在中序中寻找此结点，记录下此节点的下标位置，作为在左子树或是右子树的位置线索。

位置线索思考与整理：

        画图表，找到相关联的数字线索，做出数学公式，此处普适公式寻找比较困难，从特例开始（普朗克也是这样发现能量子的），此处思路参考了：已知后序与中序输出前序（先序） – 柳婼 の blog (liuchuo.net)https://www.liuchuo.net/archives/2090        此思路表格展示为【表头第一列为相对于其父母结点的位置，其后数字个数为所在层数+位置（左子树为1，右子树为2），root，start，fin上面已有赘述，i为root元素在中序遍历中的下标位置，n为此结点的值（最后两行是博主在写时没有列出来的，尤其是start和fin，因此博主有蒙对的嫌疑！！不过后来列表的时候居然完美吻合）】：

         因此，经过观察和统计，整理（Main 0 -> Left 1，Right 1.2 -> Left 1.2.1）左子树的计算公式为 ： ，，；

        整理（Main 0 -> Right 2，Left 1 ->Right 1.2 ）右子树的计算公式为：，，

        这样，我们就明白了整体流程（当然，博主是边想边写的，这块debug了好长时间） ，现在我们要将它写成代码。

---

 代码整理（递归）：

//
// Created by DDD on 2023/11/20.
//
#include <stdio.h>
 
void makePre(int post[], int min[], int root, int fin, int start){
    if((fin <= start)||(root<0))
        return;
    int i;
    int head = post[root];
 
    for(i=start; i<fin;i++) {
        if (min[i] == head) {
            break;
        }
    }
 
    printf(" %d",head);            //此处处理了题目中输出要求
    makePre(post,min,root-fin+i,i,start);    //左子树
    makePre(post,min,root-1,fin,i+1);        //右子树
}
 
int main(){
    int num;
    scanf("%d",&num);
    int post[num];                      //后序
    int min[num];                       //中序
    for(int i=0; i<num;i++){
        scanf("%d",&post[i]);
    }
    for(int i=0; i<num;i++){
        scanf("%d",&min[i]);
    }
    printf("Preorder:");
    makePre(post,min,num - 1,num,0);
}

---

return 0;    //归去来