二叉树三种遍历的相互转换

1.已知先序中序求后序

只要掌握各个遍历的特点，就能轻松解决问题先序:给定了根的遍历顺序中序:根的左右两边分别为左子树和右子树所以可以通过控制根的位置递归进入左子树和右子树控制格式输出即可

#include <bits/stdc++.h>
#define N 1005
using namespace std;
int a[N];int b[N];
int n;
void dfs(int l,int r,int size){
    if(size==0) return ;
    int i;
    for(i=1;i<=size;i++){
        if(a[l]==b[i+r-1]) break;
    }
    dfs(l+1,r,i-1);
    dfs(l+i,i+r,size-i);
    if(size==n) printf("%d\n",a[l]);
    else printf("%d ",a[l]);
}
int flag;
int main(){
    while(scanf("%d",&n)==1){
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<=n;i++){
            scanf("%d",&b[i]);
        }
        dfs(1,1,n);
    }
    return 0;
}

　2.已知中序后序求前序

可以根据左子树的个数在中序和后序中相等的规则可以确定进入左子树的根的位置而进入右子树的根的位置则为前一个根的位置-1 然后递归进行即可

#include <bits/stdc++.h>
#define N 1005
using namespace std;
int a[N];int b[N];
int n;
void dfs(int l,int r,int size){
    if(size==0) return ;
    if(size==n) printf("%d",a[l]);
    else printf(" %d",a[l]);
    int i;
    for(i=1;i<=size;i++){
        if(a[l]==b[r+i-1]) break;
    }
    dfs(l-(size-i+1),r,i-1);
    dfs(l-1,r+i,size-i);
}
int flag;
int main(){
      while(scanf("%d",&n)==1){
      for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<=n;i++){
           scanf("%d",&b[i]);
       }
        dfs(n,1,n);
        printf("\n");
    }
    return 0;
}

原文链接: https://www.cnblogs.com/wang9897/p/7835404.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/263414

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

二叉树三种遍历的相互转换

相关推荐