[백준 / BOJ] 1991 트리 순회

문제

출처 : www.acmicpc.net/problem/1991

1991번: 트리 순회

트리가 주어졌을때,

해당 트리를 전위순회, 중위순회, 후위순회한 결과를 출력하는 문제다.

 

풀이

트리 탐방자체는 어렵지않았는데, 입력을 트리구조로만드는게 난해한 문제였다. (순회 문제를 푼게 아니라 트리구조를 만드는 문제를 푼느낌...) 

기본적인 트리구조(idx*2, idx*2+1)에 익숙해져서인지 처음엔 그런방향으로 구현하는걸 생각했었다.

입력이 위에서부터 너비우선탐색으로 입력되는것 같아서 BFS로 입력받는 코드를 짰는데, 입력에 규칙이 없었다...

결국 다 지우고, 트리를 맵느낌으로 구현했다.(맵을 사용하지는않음)

 

트리배열을 Pair로 선언하고, first = 왼쪽 자식, second = 오른쪽 자식을 넣어줬다. 

A = {? , ?}

B = {? , ?}

.

.

.

이런 형태로 만들어놓고, first,second값을 가지고 탐색을 진행한다.

 

1. 전위순회

전위순회는 탐색순서 그대로 출력하면된다. 

 

2. 중위순회

중위순회는 하나의 자식에대해서, 끝을 찍었다면, 해당 idx를 출력해준다.

 

3. 후위순회

후위순회는 두개의 자식에 대해서 끝을 찍었다면, 해당 idx를 출력한다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1991%20%ED%8A%B8%EB%A6%AC%20%EC%88%9C%ED%9A%8C/main.cpp

devxb/JJUNalgo