[ BOJ ] 1991번 : 트리 순회

[ 문제 한줄평 ]
이진 트리에서만 쓸 수 있는 방법을 사용하였군 자네

1991번 : 트리 순회

뭐 문제 자체는 어려운게 아니다. 그냥 이진 트리 잘 저장하고 프리오더, 인오더, 포스트오더 잘 출력하면 된다.

static_cast<type>

그냥 좀 새롭게 알게 된 사실이 있는데, static_cast<type>에 대한 것이다. 형 변환을 쏙 해주는 아주 좋은놈... 쟤에 대한건 c++ 메소드 정리에 적어 두었다.

트리는 자식이 두개만 있는 것이 아니다!!!!!

문제 풀 때는 몰랐는데, 저 static_cast<type>에 대한 것을 정리하다가 깨달은 것이 있다.

트리를 표현하는 방법 중 여러 가지가 있지만, 어차피 트리도 그래프의 일종이기 때문에 그래프를 표현하는 방법과 같이 연결 리스트를 이용하라는 소리를 들었는데, 트리는 자식이 left나 right 두개안데 왜 연결리스트를 쓰라는거지? 라는 멍청한 생각을 했다.

자, 여기서 트리의 정의를 되짚어보고 가자.
트리는 자료구조의 일종으로, 사이클이 없는 그래프이다.
사이클이 없는 그래프이므로 정점의 개수가 V개일 때, 간선의 개수는 V-1개이다.

그렇다. 이진 트리는 트리의 한 종류일 뿐이다. 하나의 노드에 자식이 2개 이상일 확률은 다분하다. 단지 문제에서 친절히 왼쪽 자식이랑 오른쪽 자식만 있다고 알려줬을뿐.... 잊지말자!!!

문제 풀이

딱히 어려울게 없는 문제이므로 별도의 풀이는 생략한다 미래의 나야.

#include <iostream>
#include <vector>
using namespace std;

struct childNode
{
    int leftChild = -1;
    int rightChild = -1;
};

void preOrder(vector<childNode> &graph, int node)
{
    cout << static_cast<char>(node + 'A' - 1);

    if (graph[node].leftChild != -1)
        preOrder(graph, graph[node].leftChild);

    if (graph[node].rightChild != -1)
        preOrder(graph, graph[node].rightChild);
}

void inOrder(vector<childNode> &graph, int node)
{
    if (graph[node].leftChild != -1)
        inOrder(graph, graph[node].leftChild);

    cout << static_cast<char>(node + 'A' - 1);

    if (graph[node].rightChild != -1)
        inOrder(graph, graph[node].rightChild);
}

void postOrder(vector<childNode> &graph, int node)
{
    if (graph[node].leftChild != -1)
        postOrder(graph, graph[node].leftChild);

    if (graph[node].rightChild != -1)
        postOrder(graph, graph[node].rightChild);

    cout << static_cast<char>(node + 'A' - 1);
}

int main()
{
    int N;
    cin >> N;

    vector<childNode> graph(N + 1);

    while (N--)
    {
        char node, leftChild, rightChild;
        cin >> node >> leftChild >> rightChild;

        if (leftChild != '.')
            graph[node - 'A' + 1].leftChild = leftChild - 'A' + 1;
        if (rightChild != '.')
            graph[node - 'A' + 1].rightChild = rightChild - 'A' + 1;
    }

    preOrder(graph, 1);
    cout << "\n";
    inOrder(graph, 1);
    cout << "\n";
    postOrder(graph, 1);
}