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

아이디어

char로 들어오는 것을 받고, int로 변환하여 .은 -1로 넣고, 나머지는 숫자에 맞게 넣는다.

(A= 0, B=1,C=2 ... Z = 25)

각 벡터에 처음[0]은 왼쪽 노드고, 각벡터에 두번쨰[1]은 오른쪽 노드가 된다.

포인터로 보면 NULL노드겠지만 빈 노드를 -1로 표현했으니, -1이 ㅇ니면 travel을 계속한다.travel(int a, int type)의 type은 0,1,2로 각각 전위, 중위, 후위 순회이다.

 

C++ 풀이

#include <bits/stdc++.h>

using namespace std;
vector<int> v[26];
int N;

void travel(int a,int type){
    int p = a +'A';

    switch(type){
        case 0: //전위(preorder)
            cout << (char)p ;
            if (v[a][0] != -1) travel(v[a][0],type);
            if (v[a][1] != -1) travel(v[a][1],type);
            return;
            break;
        case 1: // 중위(inorder)
            if (v[a][0] != -1) travel(v[a][0],type);
            cout << (char)p ;
            if (v[a][1] != -1) travel(v[a][1],type);
            return;
            break;
        case 2: // 후위(postorder)
            if (v[a][0] != -1) travel(v[a][0],type);
            if (v[a][1] != -1) travel(v[a][1],type);
            cout << (char)p ;
            return;
            break;
    }
    
    
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    
    for(int i = 1; i<= N; i++)
    {
        char a, b, c;
        int a_, b_, c_;
        cin >> a >> b >> c;

        a_ = a- 'A';
        if(b != '.') b_ = b- 'A';
        else b_ = -1;
        
        if(c != '.') c_ = c- 'A';
        else c_ = -1;
        v[a_].push_back(b_);
        v[a_].push_back(c_);
    }
    
    travel(0,0);
    cout << endl;
    travel(0,1);
    cout << endl;
    travel(0,2);
}