已知后序中序输出先序

已知后序中序输出先序

题目

---

前言

老师讲的方法：

已知后序的最后一个是总的根结点，那么我们就可以把那个根结点留在那一行，然后把其他的结点落下来，然后以此类推，找到左子树的根结点和右子树的根结点，接着把其他的结点落下来.......

我原本想着按照老师讲的那种方法去编写代码，可是后来发现，刚开始我只有一个根结点，两个子树，但是子树他是会衍生子树的，我觉得这个不用递归肯定是不行的，，，

后来我就找到了这个递归的方法，链接
思路就是，我不是先序吗，先序就是根左右，那么我只要找到每个子树的根结点就可以了，剩下的就是递归的顺序了，我先打印根结点，再递归左子树，接着递归右子树，不就是先序遍历了。

接下来的问题就是如何根据后序和中序找到每个子树的根结点，我们都知道，后序的最后一个结点是总的根结点，同时后序的最后一个结点的前一个是右子树的根，我们现在只差左子树的根不知道在哪里

这样想：我们已知根结点的位置，根结点之前就是这个根结点的左右子树，那么我们只要知道了右子树所包含的结点数目，我们再用根结点的位置减去右子树所包含的结点数目，就是左子树的根结点的位置了。

问题又来了，我们怎么知道右子树所包含的结点数目，我们可以记录此次递归的范围，用start和end，当然这里是中序遍历的头和尾，由于我们每次都要根据根结点去推出左右子树的根结点，所以我们还要记录一下根结点root，这时我们就可以走一下循环，令i=0，遍历中序遍历，当循环走到当前的根结点时，循环停止，i停止++，此时我们就可以推算出右子树所包含结点的数目，即end-i，与此同时，我们一箭双雕的完成了另一个目标：规定下一次递归的范围，我们刚刚定义的i就是中序遍历中的根结点，根结点左边，也就是i-1，就是左子树的end，根结点的右边，也就是i+1，就是右子树的start

代码

#include<stdio.h>

int* back;
int* middle;

void pre(int root,int start,int end){
    if(start>end) return;//递归结束条件
    int i=start;
    //开始寻找根结点在中序遍历的位置
    //同时利用i求得左子树的根结点在后序遍历中的位置
    while(i<end&&middle[i]!=back[root]) i++;
    printf(" %d",back[root]);
    pre(root-(end-i)-1,start,i-1);
    pre(root-1,i+1,end);
}

int main(){
    int n;
    scanf("%d",&n);
    back=(int*)malloc(sizeof(int)*n);
    middle=(int*)malloc(sizeof(int)*n);
    for(int i=0;i<n;i++)
          scanf("%d",&back[i]);
    for(int i=0;i<n;i++){
        scanf("%d",&middle[i]);
    }
    printf("Preorder:");
    pre(n-1,0,n-1);

}  

原文地址：https://blog.csdn.net/Nozomi9967/article/details/144381822

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！