https://www.acmicpc.net/problem/1991
문제
> 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.
> 예를 들어 위와 같은 이진 트리가 입력되면,
> 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
> 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
> 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)
접근
입력으로 노드의 자식 관계가 주어지는데 이걸 각 노드를 인덱스로 자식을 (노드)(0), (노드)(1)로 이차원 벡터에 저장한다.
. 이면 벡터의 초기값으로 공백을 주어 그대로 공백이 남게 한다.
재귀함수로 정의한 Tree함수에 인자로 각 루트 노드가 온다.
만약 전위면 순서가 루트, 왼자식,오른자식 이므로 일단 루트 입력으로 들어온 루트노드를 출력하고 재귀로 왼자식을 루트로 해서 들어가고, 오른자식을 루트로해서 들어간다.
그럼 각각에 대해 루트, 왼, 오 순서로 출력이 된다.
예를 들면 전위일때,
1. A출력, B,C 재귀(B에 대한 재귀 끝나고 C호출)
2. B출력, D,(없음) 재귀
3. D출력, 자식없으므로 끝, B의 오른자식차롄데 없어서 2끝
4. C출력, E, F 재귀
5. E출력, 자식없으므로 끝, C오른자식 F 차례
6. F출력, (없음), G 재귀
7. G출력, 자식없으므로 끝, 6번끝, 5번끝, 4번끝, 1번 끝
최종끝
문제해결
> 자식관계를 담을 이차원 벡터 node를 문자형을 선언해준다. 크기는 노드개수가 N개이므로 N, 자식이 둘이므로 2, 초기값은 문자공백 ' '로 준다.(자식이.일때 처리)
> 관계를 입력받는다. 차례대로 첫문자는 인덱스, 두 세 번째는 왼자식 오른자식이다.
> 벡터에 인덱스는 문자가 안되므로 A를 빼서 0부터 순서대로 인덱스를 잡아 넣어준다.
> 전,중,후위 처리에 대해 각각 스위치문으로 처리하기 위해 0,1,2번의 경우로 주기위해 반복문으로 Tree를 호출하고 맨 처음 루트노드인 A를 넣어주며 두번 째 인자로 스위치문에 쓸 변수를 넣는다.
> 각각 재귀, 루트 출력을 맞게 호출해 준다.
전위 - 루트, 왼자식 재귀, 오른자식 재귀
중위 - 왼자식 재귀, 루트, 오른자식 재귀
후위 - 왼자식 재귀, 오른자식 재귀, 루트
코드
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
int N;
vector<vector<char>> node;
void Tree(char start, int t)
{
switch (t) {
case 0: //전
{
cout << start;
if (node[start - 'A'][0] != ' ') Tree(node[start - 'A'][0], 0);
if (node[start - 'A'][1] != ' ') Tree(node[start - 'A'][1], 0);
break;
}
case 1: //중
{
if (node[start - 'A'][0] != ' ') Tree(node[start - 'A'][0], 1);
cout << start;
if (node[start - 'A'][1] != ' ') Tree(node[start - 'A'][1], 1);
break;
}
case 2: //후
{
if (node[start - 'A'][0] != ' ') Tree(node[start - 'A'][0], 2);
if (node[start - 'A'][1] != ' ') Tree(node[start - 'A'][1], 2);
cout << start;
break;
}
default : break;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
node.assign(N, vector<char>(2, ' '));
while (N--)
{
char a, b, c;
cin >> a >> b >> c;
if(b != '.') node[a - 'A'][0] = b;
if(c != '.') node[a - 'A'][1] = c;
}
for (int i = 0; i < 3; i++)
{
Tree('A', i);
cout << '\n';
}
}
후기
어떻게 재귀를 쓴다는 건지에 감이 안잡혔는데 전중후의 각각 결과를 보면서 어떤 순서로 재귀가 이루어져야 이런 결과가 나올지 재귀의 흐름을 임의로 만들며 따라가 봤다.
큐, 스택에도 넣어보고 그래프탐색도 써보고 했다. 루트에 대해 처리가 이상해서 결과가 안나왔는데, 루트는 그냥 처리가 없이 출력만 해주도록 했는데 됐다.
전중후에 대해 스위치문으로 처리하는게 좀 지저분해 보여 이 부분을 압축해 봐야겠다.
