백준(BOJ) Tree 트리 순회(1991) - Silver 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개의 알파벳을 공백 없이 출력하면 된다.

문제 해결

기본적인 이진 트리 순회과정을 출력하는 문제이다. 문제 자체는 트리 자료구조를 알고 있다면 어렵지 않게 해결이 가능하나 트리 자료구조를 구현하는 부분이 조금 어려울 수 있다. c++의 경우 트리 구조체를 직접 선언해서 구현할 수 있지만 map 구조를 이용하여 트리 구조를 만들어 줄 수있다.

map은 Key, Value로 이루어진 자료구조이며 Key를 부모의 노드 Value를 왼쪽, 오른쪽 노드로 생각하여 구현하면 된다. 이 때 Value는 2개의 값이 필요하므로 2개의 값을 저장할 수  있는 구조체를 선언 또는 pair를 이용하면 된다.

map<char, pair<char, char> >tree;

• map 트리구조 부모 노드 'A'에 왼쪽 자식 노드 'B'와 오른쪽 자식 노드 'C'를 삽입하는 방법

tree['A'] = make_pair('B', 'C');

위 처럼 트리 구조를 만들기만 한다면 나머지 순회는 재귀적으로 쉽게 해결이 가능하다.

• 전위순회 - 루트가 가장 먼저
• 중위순회 - 루트가 중간
• 후위순회 - 루트가 가장 마지막

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

typedef long long ll;

void preorder(map<char, pair<char, char> >&tree, char node) {//전위순회 루-왼-오
	cout << node; //현재 노드의 데이터 출력
	if (tree[node].first != '.') { //왼쪽 자식이 있다면
		preorder(tree, tree[node].first);
	}
	if (tree[node].second != '.') { //오른쪽 자식이 있다면
		preorder(tree, tree[node].second);
	}
}

void inorder(map<char, pair<char, char> >&tree, char node) {//중위순회 왼-루-오
	if (tree[node].first != '.') { //왼쪽 자식이 있다면
		inorder(tree, tree[node].first);
	}
    cout << node; // 중간 출력
	if (tree[node].second != '.') { //오른쪽 자식이 있다면
		inorder(tree, tree[node].second);
	}
}

void postorder(map<char, pair<char, char> >&tree, char node) {//후위순회 왼-오-루
	if (tree[node].first != '.') { //왼쪽 자식이 있다면
		postorder(tree, tree[node].first);
	}
	if (tree[node].second != '.') { //오른쪽 자식이 있다면
		postorder(tree, tree[node].second);
	}
    cout << node; // 마지막 출력
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen("input.txt", "r" ,stdin);

    map<char, pair<char, char> >tree;
    ll nodes = 0;
    char node, left, right;
    cin >> nodes;

    for(ll i=0; i<nodes; i++){
        cin >> node >> left >> right;
        tree[node] = make_pair(left, right);
    }
    
    preorder(tree, 'A');
    cout << "\n";
    inorder(tree, 'A');
    cout << "\n";
    postorder(tree, 'A');
    cout << "\n";

    return 0;
}