c언어 9934번 완전 이진 트리 (백준)

#include <stdio.h> 

int arr[1<<10]; //입력 받을 배열
int ans[1<<10]; //1층은 0, 2층은 1~2, 3층은 3~6...
int p[11] = {}; //p[10] 이 전체를 가리킴 모두 각 계층의 시작 지점 (ex0, 1, 3, 7...) 을 담고 있음 
int n, m;

void loop(int v) { //inorder
	if(v < n) {
		loop(v+1);
		ans[p[v]++] = arr[p[10]++];
		loop(v+1);
	}
}

int main(void) {
	scanf("%d", &n);
	m = (1<<n)-1; //포화 이진 트리이므로 필요한 개수는 2^n-1 입니다.
	
	for(int i=0; i<m; i++) scanf("%d", &arr[i]); //트리를 이루는 요소들을, inorder 순회 한 순서로 입력받습니다.
	
	for(int i=1; i<10; i++) p[i] = (1<<i)-1; //p[]가 각 계층의 시작지점을 가리키도록 해줍니다.
	
	loop(0); //재귀를 통해, arr[]의 요소들을 계층에 맞게 ans[]에 넣어줍니다.
	
	int k = 2;
	for(int i=0; i<m; i++) {
		if(i==k-1) { //계층의 이동이 있다면 개행문자를 출력합니다.
			printf("\n");
			k<<=1; //다음 계층의 시작 값+1 을 대입
		}
		printf("%d ", ans[i]); //출력
	}
}

 

풀이 : 재귀,  이진 트리

중위 순회를 하는 문제이므로

중위 순회를 한 대로 입력을 받은 다음, 똑같이 중위 순회를 하여, 요소들을 각 계층에 맞게 입력된 순서대로 집어 넣은다음

가장 낮은 계층부터 가장 높은 계층순으로 입력받은 순서대로 출력합니다.

 

중위 순회 : 이진트리에선, 왼쪽 자식노드 방문 -> 자기자신 -> 오른쪽 자식 노드 방문 입니다.

 

일차원 배열에서 구간 나누기

0층은 0

1층은 1~2

2층은 3~6

3층은 7~14

4층은 15~30

5층은 31~63...

 

즉 층마다의 구간을

2^n-1 부터 2^(n+1)-2 로 잡으면 됩니다.

 

 

또한 입력받은 순으로 출력해야 하니, 각 층마다, 들어가야 할 곳을 가리키고 있는 변수들의 배열을 만든다음, 순서대로 들어가도록 만듧니다.

 

int p[11] = {}; //변수들을 배열로 생성한 다음

for(int i=1; i<10; i++) p[i] = (1<<i)-1; //p[]가 각 계층의 시작지점을 가리키도록 해줍니다.

ans[p[v]++] = arr[p[10]++]; //특정 계층에 들어오면 그 특정 계층을  가리키는 지점을 1 증가 시켜줍니다.

 

출력 할 때는 ans[]을 순서대로 출력 하되, 계층이 바뀔 때마다 줄바꿈을 해주면 됩니다.

 

https://www.acmicpc.net/problem/9934

9934번: 완전 이진 트리