[백준/C++]#1991 - 트리 순회

풀이

#include <iostream>
using namespace std;

int a[50][2];

void preorder (int N) {
	if (N == -1) return;
	cout << (char)(N+'A');
	preorder(a[N][0]);
	preorder(a[N][1]);
}

void inorder (int N) {
	if (N == -1) return;
	inorder(a[N][0]);
	cout << (char)(N+'A');
	inorder(a[N][1]);
}

void postorder (int N) {
	if (N == -1) return;
	postorder(a[N][0]);
	postorder(a[N][1]);
	cout << (char)(N+'A');
}

int main() {
	int n;
	cin >> n;
	for (int i=0; i<n; i++) {
		char x, y, z;
		cin >> x >> y >> z;		// 알파벳 입력
		x = x-'A';		// 문자 -> 숫자 변환
		if (y == '.') {		// 입력이 .이면 그 자리에 -1 대입
			a[x][0] = -1;
		}
		else {
			a[x][0] = y-'A';
		}
		if(z == '.') {
			a[x][1] = -1;
		}
		else {
			a[x][1] = z-'A';
		}
	}
	preorder(0);
	cout << '\n';
	inorder(0);
	cout << '\n';
	postorder(0);
	return 0;
}

개념

트리

트리는 사이클이 없는 그래프의 일종이다.

일반적으로 생각하는 나무가 뒤집어져 있는 모습이다.

뿌리, 즉 루트로부터 트리가 확장된다.

 

순회 

트리의 모든 노드를 방문하기 위해 순회를 하는데, 순회 순서는 3가지 방법으로 나뉜다.

각각 preorder (전위 순회), inorder (중위 순회), postorder (후위 순회) 이다.

전위 / 중위 / 후위

전위 : 노드->왼쪽->오른쪽

중위 : 왼쪽->노드->오른쪽

후위 : 왼쪽->오른쪽->노드

 

덩어리처럼(서브트리) 생각해서 접근하면 순회 순서를 생각하기가 쉬워진다.

---

문자를 숫자로, 숫자를 문자로 바꿔야한다.

 

①입력이 A~Z이므로 x = x-'A'; 를 사용하면 0~26의 수를 얻을 수 있다.

② (char) (N + 'A') 를 통해 0~26의 수를 A~Z로 표현한다.

 

---

풀이

 

먼저 입력을 받아야한다.

배열에 참조할 노드 값을 저장한다.

 

예시로, 루트: A  왼노드: B  오른노드: C 가 입력된다.

a[A][0] = B

a[A][1] = C

 

이런 방식으로 저장된다.

이제 A(문자) 값을 정수형 index로 바꿔주면 된다.

 

a[0][0] = 1;

a[0][1] = 2;

 

이렇게 입력받은 트리를 배열에 저장한다.

공백을 의미하는 . 이 입력되면 index를 -1 값으로 한다.

문제의 예시 값을 모두 저장한 모습

 

이제 순회하면 된다.

순회의 종류는 순환 호출의 순서에 따라 달라진다.

적절한 위치에서 노드를 순회하는 순환 호출을 사용한다.

 

전위 : 현재 노드 출력 -> 왼쪽 노드 순회 -> 오른쪽 노드 순회

중위 : 왼쪽 노드 순회 -> 현재 노드 출력 -> 오른쪽 노드 순회

후위 : 왼쪽 노드 순회 -> 오른쪽 노드 순회 -> 현재 노드 출력