二叉树的各类遍历转化

1.转化规则:

在二叉树

1.中序+前序,中序+后序,中序+层序可以唯一确定一棵二叉树

2.前序 + 后续 不一定能确定一颗二叉树

2.具体实现

1.根据中序 + 前序 确定后续

#include<vector>
#include<cstdio>
using namespace std;

vector<int> pre;
vector<int> in;
void post(int prel,int inl,int inr){
 if(inl > inr) return ;
 int i = inl;
 while(in[i] != pre[prel] && i <= inr) i++;
 post(prel + 1,inl,i - 1);
 post(prel + (i - inl) + 1,i + 1,inr);
 printf("%d ",in[i]);
}

int main(){
 int a;
 scanf("%d",&a);
 pre.resize(a);
 in.resize(a);
 for(int i = 0;i < a;i++) scanf("%d",&pre[i]);
 for(int i = 0;i < a;i++) scanf("%d",&in[i]);
 post(0,0,a - 1);

}

2.后续 + 中序 确定前序

#include<vector>
#include<cstdio>
using namespace std;
vector<int> post;
vector<int> in;


void pre(int postr,int inl,int inr){
 if(inl > inr) return ;
 int i = inl;
 while(in[i] != post[postr] && i >= inl) i++;
 printf("%d ",in[i]);
 pre(postr-(inr - i) - 1,inl,i - 1);
 pre(postr - 1,i + 1,inr);

}
int main(){
 int a;
 scanf("%d",&a);
 post.resize(a);
 in.resize(a);
 for(int i = 0;i < a;i++) scanf("%d",&post[i]);
 for(int i = 0;i < a;i++) scanf("%d",&in[i]);
 pre(a - 1,0,a - 1);


}

3.前序 + 后续 得到其中一中序,题型来自PAT A1119

#include<vector>
#include<cstdio>
using namespace std;

vector<int> pre;
vector<int> post;
vector<int> in;

int flg = 0;
void intt(int prel,int prer,int postl,int postr){
 if(postr < postl) return;
 int i = prel + 1;
 while(post[postr - 1] != pre[i] && i <= prer) i++;
 if((i - 1) == prel && i <= prer){
 flg = 1;
 }
 intt(prel + 1,i - 1,postl,postl + (i - 2 - prel));//默认为右子树
 in.push_back(post[postr]);
 intt(i,prer,postl + (i - 1 - prel),postr - 1);

}

int main(){
 int a;
 scanf("%d",&a);
 pre.resize(a);
 post.resize(a);
 for(int i = 0;i < a;i++) scanf("%d",&pre[i]);
 for(int i = 0;i < a;i++) scanf("%d",&post[i]);
 intt(0,a - 1,0,a - 1);
 printf("%s\n%d",flg == 1 ? "No":"Yes",in[0]);
 for(int i = 1;i < in.size();i++){
 printf(" %d",in[i]);
 }
 return 0;
}

4.中序+前序,确定层序(PAT A1127)

#include<vector>
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;

vector<int> in;
vector<int> post;
int level[10000];
int last = 0;
void creatree(int sig,int inl,int inr,int postr){//post + in = level
 while(inl > inr) return;
 int i = inl;
 if(last < sig)
 last = sig;
 level[sig] = post[postr];
 while(in[i] != post[postr] && i <= inr) i++;
 creatree(sig * 2 + 1,inl,i - 1,postr - (inr - i) - 1);
 creatree(sig * 2 + 2,i + 1,inr,postr - 1);
}
int towx(int a){
 int re = 1;
 for(int i = 0;i < a;i++){
 re *= 2;
 }
 return re;
}
int main(){
 int a;
 cin >> a;
 in.resize(a);
 post.resize(a);

fill(level,level + 10000,-1);
 for(int i = 0;i < a;i++) cin >> in[i];
 for(int i = 0;i < a;i++) cin >> post[i];
 creatree(0,0,a - 1,a - 1);

int i = 0;
 int k = 1;//cengshu
 int u = 0;
 while(i <= last){
 if(k % 2 == 0){
 for(int j = 0;j < towx(k - 1);j++){
 if(level[j + i] != -1 && u == a - 1){
 cout <<level[j + i];
 }
 if(level[j + i] != -1 && u != a - 1){
 cout <<level[j + i]<<" ";
 u++;
 }

}
 }
 if(k % 2 == 1){
 for(int j = towx(k - 1) - 1;j >= 0;j--){
 if(level[j + i] != -1 && u == a - 1){
 cout <<level[j + i];
 }
 if(level[j + i] != -1&& u != a - 1){
 cout <<level[j + i]<<" ";
 u++;
 }

}
 }
 i += towx(k - 1);
 k ++;
 }

}

5.层遍历(PAT A1004)

#include<vector>
#include<cstdio>
using namespace std;
const int maxi = 100;
vector<int> v[maxi];
int ans[maxi];

void layer(int i,int s){
 if(v[i].size() == 0)
 ans[s]++;
 for(int j = 0;j < v[i].size();j++)
 layer(v[i][j],s + 1);
}

int main(){
 fill(ans,ans + maxi,-1);
 int a,b,c,d,e;
 int i,j,k;
 scanf("%d %d",&a,&b);
 for(int i = 0;i < b;i++){
 scanf("%d %d",&c,&d);
 for(int j = 0;j < d;j++){
 scanf("%d",&e);
 v.push_back(e);
 }
 }
 // printf("creat tree finished\n");
 //ceng bian li
 if(a == 1){
 printf("1");
 return 0;
 }else{
 layer(1,0);
 printf("0");
 }

 for(i = a;i >= 0;i--){
 if(ans[i] != -1){
 k = i;
 break;
 }
 }
 for(i = 1;i <= k;i++){
 if(ans[i] != -1)
 printf(" %d",ans[i] + 1);
 else
 printf(" 0");
 }
 return 0;
}

 

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注