백준 1991 - 트리 순회(C++)

문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 문제이다.

• 전위 순회 : (루트)(왼쪽 자식)(오른쪽 자식)
  
  
• 중위 순회 : (왼쪽 자식)(루트)(오른쪽 자식)
  
  
• 후위 순회 : (왼쪽 자식)(오른쪽 자식)(루트)

입력

첫째 줄에 이진 트리의 노드의 개수 N이 주어진다. (1 <= N <=26)

 

둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식, 오른쪽 자식 노드가 주어진다.

 

자식 노드가 없는 경우에는 '.'으로 표현한다.

 

예제 입력

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

 

예제 출력

ABDCEFG
DBAECFG
DBEGFCA

문제 해결

어디서 힌트를 얻을 수 있을까?

 

'트리를 순회'한다는 말이 곧 키워드가 된다. 이 말은 곧 그래프의 DFS랑 다를게 없다.

 

즉, 재귀를 돌면서 원하는 작업을 해주면 되는데 그 작업마저도 문제에 전부 다 나와있는 셈이다.

• 전위 순회 : (루트)(왼쪽 자식)(오른쪽 자식)
  
  
• 중위 순회 : (왼쪽 자식)(루트)(오른쪽 자식)
  
  
• 후위 순회 : (왼쪽 자식)(오른쪽 자식)(루트)

이 말을 따라서 코드를 구현하면 된다.

 

코드

#include <iostream>
#include <vector>

std::vector<int> varr[27];

void preOrder(int S)
{
	std::cout << (char)(S + 'A');
	if (varr[S][0] >= 0)
		preOrder(varr[S][0]);
	if (varr[S][1] >= 0)
		preOrder(varr[S][1]);
}

void inOrder(int S)
{
	if (varr[S][0] >= 0)
		inOrder(varr[S][0]);
	std::cout << (char)(S + 'A');
	if (varr[S][1] >= 0)
		inOrder(varr[S][1]);
}

void postOrder(int S)
{
	if (varr[S][0] >= 0)
		postOrder(varr[S][0]);
	if (varr[S][1] >= 0)
		postOrder(varr[S][1]);
	std::cout << (char)(S + 'A');
}


int main(void)
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	int N;
	std::cin >> N;
	for (int i = 0; i < N; i++)
	{
		char R, LN, RN;
		std::cin >> R >> LN >> RN;
		if (LN == '.')
			LN = 0;
		if (RN == '.')
			RN = 0;
		varr[(int)(R - 'A')].push_back((int)(LN - 'A'));
		varr[(int)(R - 'A')].push_back((int)(RN - 'A'));
	}
	preOrder(0);
	std::cout << "\n";
	inOrder(0);
	std::cout << "\n";
	postOrder(0);
	std::cout << "\n";
	return 0;
}

 

문제 출처

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

1991번: 트리 순회