BOJ 1991번 트리 순회

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

GitHub : https://github.com/junho0956/Algorithm/blob/master/1991/1991/%EC%86%8C%EC%8A%A4.cpp

 

트리순회의 기본은 전위순회, 중위순회, 후위순회이다.

각 순회의 방법은 자신의 자식을 보며 움직이는 것으로 코드로 구현해놓았으니 참고하면 될 것 같다.

처음에는 구조체를 이용해서 동적 트리를 직접 만들려고 했지만

그러기엔 각 알파벳을 찾아가야하는 단점이 있어 구조체배열을 이용해서 해결하였다.

 

#include <iostream>
#include <vector>
using namespace std;
 
struct node {
    char my;
    char left = NULL, right = NULL;
    bool visit = false;
}node[26];
 
void pre_order(char ch) {
    if (node[ch - 'A'].visit == true) return;
    node[ch - 'A'].visit = true;
    cout << ch;
    if (node[ch - 'A'].left != NULL) pre_order(node[ch - 'A'].left);
    if (node[ch - 'A'].right != NULL) pre_order(node[ch - 'A'].right);
}
 
void in_order(char ch) {
    if (node[ch - 'A'].visit == true) return;
    node[ch - 'A'].visit = true;
 
    if (node[ch - 'A'].left != NULL) in_order(node[ch - 'A'].left);
    cout << ch;
    if (node[ch - 'A'].right != NULL) in_order(node[ch - 'A'].right);
}
 
void post_order(char ch) {
    if (node[ch - 'A'].visit == true) return;
    node[ch - 'A'].visit = true;
    
    if (node[ch - 'A'].left != NULL) post_order(node[ch - 'A'].left);
    if (node[ch - 'A'].right != NULL) post_order(node[ch - 'A'].right);
    cout << ch;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int N; cin >> N;
    char ch, chl, chr;
    for (int i = 0; i < N; i++) {
        cin >> ch >> chl >> chr;
        node[ch - 'A'].my = ch;
        if(chl != '.') node[ch - 'A'].left = chl;
        if(chr != '.') node[ch - 'A'].right = chr;
    }
 
    pre_order('A'); cout << '\n';
    for (int i = 0; i < N; i++) node[i].visit = 0;
    in_order('A'); cout << '\n';
    for (int i = 0; i < N; i++) node[i].visit = 0;
    post_order('A');
 
    return 0;
}