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

『목차』
0. 개요
1. 문제
2. 풀이
3. 코드

0. 개요

트리, 재귀 문제. 트리를 순회하는 가장 기본적인 방법인 '전위 순회', '중위 순회', '후위 순회'에 대해 알고있다면 쉽게 풀 수 있는 문제이다.

1. 문제

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

1991번: 트리 순회

[문제]

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

[입력]

첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.

[출력]

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

[예제 입력 1]

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

[예제 출력 1]

ABDCEFG
DBAECFG
DBEGFCA

반응형

2. 풀이

전위 순회, 중위 순회, 후위 순회란 무엇일까? 

* 트리 순회란 특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 말한다.

* 트리 구조는 계층적 구조라는 특별한 특징을 가지기 때문에, 모든 노드를 순회하는 방법엔 크게 세가지가 있다.

* 위의 세가지 방법이 바로 전위 순회, 중위 순회, 후위 순회 이다. (순회 순서는 아래 그림과 같다.)

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

핵심 코드만 살펴보자.

tree 배열의 0번째 index 에는 A 노드의 정보가 저장되고, 1번째 idx에는 B 노드, 2번째 idx에는 C 노드, ..., 25번째 idx에는 Z 노드가 저장된다.

여기서, tree[root - 'A'] 라는 방식으로 root 값에 해당하는 노드를 배열에 순차적으로 저장할 수 있게 된다.

3. 코드

#include <iostream>
using namespace std;

/* Struct */
struct node {
	char left;
	char right;
};

/* Global */
node tree[26]; // A(0)~Z(26) 까지 저장.

/* Function */
void preorder(char root) { //전위순회
	if (root != '.') {
		cout << root;
		preorder(tree[root - 'A'].left);
		preorder(tree[root - 'A'].right);
	}
}

void inorder(char root) { //중위순회
	if (root != '.') {
		inorder(tree[root - 'A'].left);
		cout << root;
		inorder(tree[root - 'A'].right);
	}
}

void postorder(char root) { //후위순회
	if (root != '.') {
		postorder(tree[root - 'A'].left);
		postorder(tree[root - 'A'].right);
		cout << root;
	}
}

/* Main */
int main(int argc, char* argv[]) {
	/* Faster */
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	/* Input & Init */
	int n; cin >> n;
	for (int i = 0; i < n; i++) {
		/* Input */
		char root, left, right;
		cin >> root >> left >> right;
		/* Tree */
		tree[root - 'A'].left = left;
		tree[root - 'A'].right = right;
	}

	/* Output */
	preorder('A');
	cout << '\n';
	inorder('A');
	cout << '\n';
	postorder('A');
	cout << '\n';
		
	/* Return */
	return 0;
}