Boj 1991 c++ 트리순회

**정확하지 않은 내용을 담고 있을 수 있습니다**

 

문제는 다음과 같다

 

위와 같은 이진트리가 있을 때 트리를 전위 순회, 중위 순회, 후위 순회한 결과 값을 출력하는 문제이다.

 

전위순회는 트리의 루트, 왼쪽 자식, 오른쪽 자식을 차례대로 순회하는 것이고, 

중위순회는 트리의 왼쪽 자식, 루트, 오른쪽 자식을 차례대로 순회하는 것, 

후위순회는 왼쪽 자식, 오른쪽 자식, 루트 노드를 차례대로 방문하는 것이다.

 

이는 재귀 호출로 구현이 가능하다.

 

배열을 두 개 선언한 후, 입력되는 문자에 따라서 인덱싱(보정)을 해준다.

ABCD,와 같이 알파벳 순서대로 번호가 매겨지기 때문에 해당 문자의 알파벳에서 A를 뺀 값이 해당 노드의 번호가 된다.

그 후, 매겨진 번호에 따라 연결 처리를 해주고, 최종적으로 순회 종류에 따라 함수를 구현해주면 끝난다.

 

작성한 코드는 다음과 같다.

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

vector<char> v;
vector<vector<int>> connected;

void preorder(int n) {
    if (n == -1)return; //더이상 자식노드가 없으면 탈출
    cout << v[n];
    preorder(connected[n][0]);
    preorder(connected[n][1]);
}
void inorder(int n) {
    if (n == -1)return;
    inorder(connected[n][0]);
    cout << v[n];
    inorder(connected[n][1]);
}
void postorder(int n) {
    if (n == -1)return;
    postorder(connected[n][0]);
    postorder(connected[n][1]);
    cout << v[n];
}
int main(){

    int n; cin >> n; //노드 개수 입력 받기
    v.resize(n+1); connected.resize(n+1);
    for(int i = 0 ; i < n; i++) {
        char root, x, y;
        cin >> root >> x >> y; //부모노드, 자식노드
        int idx = root-'A';
        v[idx] = root;
        if (x != '.') {
            connected[idx].push_back(int(x-'A'));
        } else {
            connected[idx].push_back(-1);
        }
        if (y != '.') {
            connected[idx].push_back(int(y-'A'));
        } else {
            connected[idx].push_back(-1);
        }

    }
    preorder(0);
    cout << "\n";
    inorder(0);
    cout << "\n";
    postorder(0);

}