[TREE] 백준 1991번 트리의 순회(C++)

https://www.acmicpc.net/problem/1991

 

트리 순회 문제다.

 

아마 개발자를 목표로 하는 취준생이나, 대학생 3~4학년이라면 당연히 전위 중위 후위순위에 대한 알고리즘을 알고 있을 거다.

 

간단히 설명하자면, 트리를 탐색할 때

문제에 나온 것처럼

 

루트 , 왼쪽자식 ,오른쪽 자식

순서대로 찾아볼거냐

 

왼쪽자식 루트 오른쪽 자식

 

or

 

왼쪽 오른쪽 루트 

 

방식으로 찾아볼거냐에 대한 것이다.

 

그래서 전위순회를 한 경우에는 

가장 먼저 A에서 시작하므로 루트 A를출력

그 이후 왼쪽노드로 넘어가면

B가 루트노드가되므로 B 출력

그 이후 D 가...

이렇게 반복하는 것이다

 

이런 문제는 재귀를 통해서 풀면 되는데

 

진입점에 따라 탐색 방식이 달라진다고 생각하면 된다.

 

예를들어

 

1.왼쪽노드 들어가기

2.오른쪽노드 들어가기

3.루트 탐색

이라는 선택지가 있다고 하자

 

전위순회는

3 -> 1-> 2

 

중위 순회는 

1->3->2

 

후위순회는

1->2->3

이다.

 

#include <iostream>

#include <queue>

#include <stack>

#include <vector>

using namespace std;

vector<char> v[27];

void pre(char temp);

void pos(char temp);

void ino(char temp);

int main()

{

    int n;

    cin >> n;

    for (int i = 1; i <= n; i++)

    {

        char parent, c1, c2;

        cin >> parent >> c1 >> c2;

        int par = parent - 'A' + 1;

        v[par].push_back(c1);

        v[par].push_back(c2);

    }

   

    pre('A');

    cout << "\n";

    pos('A');

    cout << "\n";

    ino('A');

}

void pre(char temp)

{

    cout << temp;

    int index = temp - 'A' + 1;

    for (int i = 0; i < 2; i++)

    {

        char child = v[index][i];

        if (!(child == '.'))

            pre(child);

    }

}

void pos(char temp)

{

    int index = temp - 'A' + 1;

    char child = v[index][0];

    if (!(child == '.'))

        pos(child);

    cout << temp;

    child = v[index][1];

    if (!(child == '.'))

        pos(child);

}

void ino(char temp)

{

    int index = temp - 'A' + 1;

    char child = v[index][0];

    if (!(child == '.'))

        ino(child);

    child = v[index][1];

    if (!(child == '.'))

        ino(child);

   

    cout << temp;

}

어렵지 않다.