PTA L2-011 두 갈래 나무 돌리기 (25점)

L2-011 두 갈래 나무(25분)를 돌려서 두 갈래 나무의 중차순과 전차순을 정해 줍니다. 먼저 나무를 거울로 반전시킨 다음에 반전 후의 층차순의 서열을 출력해 주십시오.거울 반전이란 모든 비엽결점의 좌우 아이를 맞바꾸는 것을 말한다.여기서 키 값이 서로 같지 않은 정수라고 가정합니다.
입력 형식: 첫 번째 줄을 입력하면 정수 N(≤30)을 주고 두 갈래 나무의 결점의 개수입니다.두 번째 줄은 그 중의 서열을 반복한다.세 번째 줄은 앞의 순서를 반복해서 보여 준다.숫자 사이는 공백으로 구분된다.
출력 형식: 한 줄에서 이 트리가 반전된 후 겹쳐진 시퀀스를 출력합니다.숫자 사이는 1개의 공백으로 구분되며, 줄의 앞뒤에 여분의 공백이 있어서는 안 된다.
샘플 입력: 7 1 2 3 4 5 6 7 4 1 3 2 6 5 7
출력 예: 4 6 1 7 5 3 2

생각

1. 우선, 선순, 중순으로 나무를 세운다.하나의 수조로 트리를 저장하고 루트 노드를 입력한 다음에 왼쪽 트리를 입력하고 오른쪽 트리를 입력하십시오.

 ， ， ， 
void creatT(int *xian,int *zhong,int n,int index){
	if(n==0) return ;// 
	int k=0;
	while(xian[0]!=zhong[k]) k++;
	tree[index]=xian[0];// 
	creatT(xian+1,zhong,k,index*2);// 
	creatT(xian+k+1,zhong+k+1,n-k-1,index*2+1);//  
}
 ， +1， k
 ， +k+1, n-k-1, 

2.tree[]수조의 순서를 출력하는 것은 층차적으로 훑어보는 것이지만 뒤집어야 하기 때문에 대열의 순서로 훑어보고 입대할 때 오른쪽 나무를 먼저 고려하고 왼쪽 나무를 생각하면 된다.코드

#include
using namespace std;
int n,t=0;
int xian[100],zhong[100];
int tree[10000],tree1[10000];
void creatT(int *xian,int *zhong,int n,int index){
	if(n==0) return ;
	int k=0;
	while(xian[0]!=zhong[k]) k++;
	tree[index]=xian[0];
	creatT(xian+1,zhong,k,index*2);//  
	creatT(xian+k+1,zhong+k+1,n-k-1,index*2+1);//  
}
void level(){
	queue<int> q;
	q.push(1);// 
	while(!q.empty()){
		int p=q.front();
		q.pop();
		tree1[t++]=tree[p];// 
		// ， 
		if(tree[p*2+1]!=0) q.push(p*2+1);//  
		if(tree[p*2]!=0) q.push(p*2);//  
	}
}
int main(){
     scanf("%d",&n);
	 for(int i=0;i<n;i++) scanf("%d",&zhong[i]);
     for(int i=0;i<n;i++) scanf("%d",&xian[i]);    
     creatT(xian,zhong,n,1);
     level();
     for(int i=0;;i++){
     	if(tree1[i]==0) break;
     	if(i==0) printf("%d",tree1[i]);
     	else if(i!=0) printf(" %d",tree1[i]);
     }
}

궁금한 게 있으면 댓글로 같이 소통하세요.