[트리] 순회 결과 값으로 이진트리 만들기

관련 문제

-이진 검색 트리: www.acmicpc.net/problem/5639 (전위->이진트리)

-완전 이진 트리: www.acmicpc.net/problem/9934 (중위->이진트리)

---

이진 검색 트리 문제부터 본다

전위 순회한 결과 값으로 후위 순회하는 문제이다

 

전위 순회는 루트-왼쪽-오른쪽 순으로 방문한다

이진 트리는 들어온 값을 루트부터 시작하여 값이 큰지 작은지 비교, 왼쪽/오른쪽 어느 서브 트리로 보낼지를 결정해야 한다

이 문제에서 전위 순회 결과로 이진트리를 만드는 작업은 다음과 같이했다(참고: www.acmicpc.net/problem/1539 )

 

1. 전위 순회는 무조건 첫 값이 루트이므로 첫 값은 루트로 넣는다

2. 값을 하나 입력 받는다

3. 현재 노드를 나타낼 now변수를 둔다. now는 계속 갱신될 것이며 초기값은 root이다

4. while문을 돌면서 입력값 n과 현재값 now를 비교한다. 작으면 왼쪽으로 크면 오른쪽으로 순회한다

5. 순회할 서브 트리가 없으면 n값으로 새로운 노드를 만든다

 

<전위 순회 결과 값으로 이진 트리 만들기>

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <memory.h>
using namespace std;
int n;
struct Node {
	int left, right;
};
vector<Node> tree(1000001);

void postorder(int now) {
	if (now == 0) return;
	if (tree[now].left != 0) postorder(tree[now].left);
	if (tree[now].right != 0) postorder(tree[now].right);
	cout << now << "\n";
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, root;
	cin >> root; //첫 값은 root
	while (cin >> n) { //입력이 있을 때만 반복문 실행
		int now = root; //지금 탐색 위치
		while (1) {
			if (n < now) {
				if (tree[now].left != 0) now = tree[now].left; //노드가 있으면 더 탐색
				else { //노드가 없으면 생성 후 종료
					tree[now].left = n;
					break;
				}
			}
			else {
				if (tree[now].right != 0) now = tree[now].right;
				else {
					tree[now].right = n;
					break;
				}
			}
		}
	}
	postorder(root);
}

그렇게 만들어진 이진 트리로 후위 순회를 돌리면 된다

 

그럼 이제 완전 이진 트리 문제를 본다

이 문제는 중위 순회 결과 값으로 이진트리를 만들고 레벨 별로 출력하는 문제이다

'순회 결과로 이진 트리를 만들고 출력한다'부분이 위의 문제와 동일하니까 같은 방법으로 접근했다

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <memory.h>
using namespace std;
struct A {
	char left, right;
};
vector<A> v(100);

void go(int now) { //중
	if (v[now].left != 0) go(v[now].left);
	cout << now << "\n";
	if (v[now].right != 0) go(v[now].right);
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	cin >> n;
	int nn = pow(2, n) - 1;
	for (int i = 0; i < nn; i++) {
		int a;
		cin >> a;
		while (1) {
			int now = a;
			//int now = root; //루트??
			if (n < now) {
				if (v[now].left != 0) now = v[now].left; //왼쪽 노드가 있으면 순회
				else {
					v[now].left = a; //없으면 만듦
					break;
				}
			}
			else {
				if (v[now].right != 0) now = v[now].right; //오른쪽 노드가 있으면 순회
				else {
					v[now].right = a; //없으면 만듦
					break;
				}
			}
		}
	}
	go(6); //테스트용
}

그런데 여기서 문제가 생겼다 바로 루트를 모른다는 점ㅜㅜ

이전 문제처럼 while로 반복문을 시작하려면 현재 노드와 계속 비교해 나가야 하는데, 그 기준이 되는 첫 값인 root값을 알 수가 없었다

 

다른 문제에서 루트값을 알 수 없을 때 루트를 구했던 방법도 생각했는데(참고: www.acmicpc.net/problem/2250)

루트를 구할 수 있던 이유는 입력부터 왼쪽/오른쪽 자식으로 나왔던 값을 체크했고, 이후 반복문을 돌면서 한 번도 자식 노드로 언급되지 않았던 노드를 root라고 구했던 것이다

if (y != -1) findroot[y]++; //값이 있으면 체크
if (z != -1) findroot[z]++;	
        
int root; //자식 노드로 한 번도 언급되지 않은 노드가 루트
for (int i = 1; i <= n; i++) if (findroot[i] == 0) root = i;

 

이번 문제에서는 입력값 자체가 이미 순회된 값이니 이 방법도 쓸 수 없었다

 

그래서 찾아봤는데.. 그냥 엄청 간단하게 되는 거였다

참고로 이 문제는 입력값으로 최대 레벨이 주어졌다

 

<중위 순회 결과 값으로 이진 트리 만들기>

void go(int now, int depth) {
	if (depth == n) res[now] = v[cnt++]; //마지막값
	else {
		go(now * 2, depth + 1); //왼
		res[now] = v[cnt++]; //현재
		go(now * 2 + 1, depth + 1); //우
	}
}

 

1. 마지막 레벨이라면 마지막 노드값 넣어주고 끝

2. 마지막 레벨이 아니라면 왼쪽 자식 탐색

3. 현재 노드에 값 넣기

4. 오른쪽 자식 탐색

 

현재값과 입력값이 크냐작냐 비교할 필요도 없이 그냥 순회 돌면서 새로운 트리를 만들어주면 되었다..

위의 문제도 이 코드에서 순서만 바꿔주면 while문 길게 안 쓰고도 될 것 같다

 

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <memory.h>
#include <math.h>
using namespace std;
vector<int> v(1024), res(1024);
int n;
int cnt = 0;
void go(int now, int depth) {
	if (depth == n) res[now] = v[cnt++]; //마지막값
	else {
		go(now * 2, depth + 1); //왼
		res[now] = v[cnt++]; //현재
		go(now * 2 + 1, depth + 1); //우
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	int nn = pow(2, n) - 1;
	for (int i = 0; i < nn; i++) {
		cin >> v[i];
	}
	go(1, 1);
	int cnt = 1;
	for (int i = 0; i < n; i++) {
		int len = 1;
		for (int j = 0; j < i; j++) len *= 2; //개수
		for (int j = 0; j < len; j++) {
			cout << res[cnt++] << " ";
		}
		cout << "\n";
	}
}

 

참고로 이 문제 상위권 코드(www.acmicpc.net/source/6485380)를 보니까 더 빨리 만들 수 있는 방법이 있다

홀수 인덱스 값들을 맨 마지막 레벨로 넣은 후, 짝수 인덱스 값들을 하나의 레벨로 생각하고 그 줄에서 다시 홀수 인덱스가 다음 레벨이 된다

반복문 돌면서 짝/홀 비교해서 트리를 새로 만들어주면 되더라