트리 순회

문제: 트리 순회 (백준 1991번)

구조 분석

해당 문제는 전형적인 tree문제이다. 이는 tree 순회문제로 자료구조의 기본이 되는 내용이다. 트리를 순회하는 방법은 다음과 같다.

pre order: (root) (left) (right) 순서로 순회
in order: (left) (root) (right) 순서로 순회
post order: (left) (right) (root) 순서로 순회  

풀이 방법

해당 문제를 푸는 방법으로는 구조체를 생성하여 노드 별로 left child와 right child를 저장해야 한다. 자식 노드를 저장할 때, 구조체 포인터를 이용할 수도 있지만 해당 문제에서는 노드의 범위가 26글자로 한정적이어서 포인터 대신 vector를 이용하여 전체 노드를 저장한 뒤 탐색을 수행하기로 했다.

코드

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#define MAX 26
using namespace std;

int n;
typedef struct Node {
    char left;
    char right;
} Node;
vector<Node> V(26); 

void pre(char node) {
    if (node == '.') return;
    cout << node;
    pre(V[node].left);
    pre(V[node].right);
}

void in(char node) {
    if (node == '.') return;
    in(V[node].left);
    cout << node;
    in(V[node].right);
}

void post(char node) {
    if (node == '.') return;
    post(V[node].left);
    post(V[node].right);
    cout << node;
}

int main() {
    cin >> n;
    for (int i=0; i<n; i++) {
        char root, l, r;
        cin >> root >> l >> r;
        V[root].left = l;
        V[root].right = r;
    }
    pre('A');
    cout << "\n";
    in('A');
    cout << "\n";
    post('A');
    cout << "\n";

    return 0;
}  

정리

해당 문제에서는 vector를 이용하여 트리를 저장하고 순회하는 것을 연습해봤다. 여러 코드들을 찾아보다가 재미있는 vector 사용법이 있었다.

vector['A']와 같이 vector를 char로 인덱스를 주고 탐색할 수 있다.  

예를 들어 문제 사진의 예제 입력1의 경우에서  
vector['B'].left를 출력하면 D가 출력되고
vecotr['F'].right를 출력하면 G가 출력된다.