BOJ : 1991 트리 순회

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

트리 순회 문제입니다.

각 순회에 대한 정의는 위키피디아를 참조했습니다.

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C

전위 순회

전위 순회(preorder)는 다음과 같은 방법으로 진행한다. 루트 노드에서 시작해서,

1. 노드를 방문한다.
2. 왼쪽 서브 트리를 전위 순회한다.
3. 오른쪽 서브 트리를 전위 순회한다.

전위 순회는 깊이 우선 순회(depth-first traversal)라고도 한다.

중위 순회

중위 순회(Inorder Traversal)은 다음의 순서로 진행된다.

1. 왼쪽 서브 트리를 중위 순회한다.
2. 노드를 방문한다.
3. 오른쪽 서브 트리를 중위 순회한다.

중위 순회는 대칭 순회(symmetric traversal)라고도 한다.

후위 순회

후위 순회(postorder)는 다음과 같은 방법으로 진행한다.

1. 왼쪽 서브 트리를 후위 순회한다.
2. 오른쪽 서브 트리를 후위 순회한다.
3. 노드를 방문한다.

레벨 순서 순회도 있는데 흔히 알고 있는 너비 우선 탐색(BFS)를 말합니다.

위 정의처럼 순회 하는 함수를 만들고 순회중인 노드의 출력 위치를 어디 두느냐에 따라 순회 방법이 정해집니다.

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

int N;
vector<pair<char, char>> v[26];

void preOrder(char root){
    char left = v[root-'A'].front().first;
    char right = v[root-'A'].front().second;
    
    printf("%c",root);
    if(left != '.') preOrder(left);
    if(right != '.') preOrder(right);
}

void inOrder(char root){
    char left = v[root-'A'].front().first;
    char right = v[root-'A'].front().second;
    
    if(left != '.') inOrder(left);
    printf("%c",root);
    if(right != '.') inOrder(right);
}

void postOrder(char root){
    char left = v[root-'A'].front().first;
    char right = v[root-'A'].front().second;
    
    if(left != '.') postOrder(left);
    if(right != '.') postOrder(right);
    printf("%c",root);
}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        char n,l,r;
        scanf(" %c %c %c",&n,&l,&r);
        v[n-'A'].push_back(make_pair(l,r));
    }
    
    preOrder('A');
    printf("\n");
    inOrder('A');
    printf("\n");
    postOrder('A');
    printf("\n");
    
}