백준 1991번: 트리 순회

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

참고한 블로그 : https://cocoon1787.tistory.com/472

---

이진 트리 정보를 입력받아서 전위, 중위, 후위 순회를 한 결과를 출력하는 문제이다.

전위 : 루트 -> 왼쪽 -> 오른쪽
중위 : 왼쪽 -> 루트 -> 오른쪽
후위 : 왼쪽 -> 오른쪽 -> 루트

루트의 위치가 어디에 있느냐로 전 중 후가 나뉜다.

트리 문제를 거의 안풀어봐서 트리 구조체를 구현을 해야 하나 싶어 검색을 하고 문제를 풀게 되었다. 간단하게 순서만 출력하는 문제라 따로 구현을 안 했나보다..?

알파벳 대문자로 최대 26개를 저장할 것이고, 왼쪽 자식과 오른쪽 자식으로 2개의 정보가 더 필요하기 때문에 char tree[26][2] 배열을 선언하고 저장을 해 주었다.

재귀 함수를 이용해서 전위 중위 후위 순회 함수를 각각 만들어 주었다.
출력하는 순서에 맞춰서 루트면 출력, 왼쪽 또는 오른쪽 자식이면 재귀 호출을 통해 순서대로 방문할 수 있도록 했다.

---

<작성한 코드>

#include <iostream>
using namespace std;

int n;
char tree[26][2];

void preorder(char root){ // 전위 -> 루트, 왼, 오
    if(root == '.')
        return ;
    cout << root;
    preorder(tree[root - 'A'][0]);
    preorder(tree[root - 'A'][1]);
}

void inorder(char root){ // 중위 -> 왼, 루트, 오
    if(root == '.')
        return ;
    inorder(tree[root - 'A'][0]);
    cout << root;
    inorder(tree[root - 'A'][1]);
}

void postorder(char root){ // 후위 -> 왼, 오, 루트
    if(root == '.')
        return ;
    postorder(tree[root - 'A'][0]);
    postorder(tree[root - 'A'][1]);
    cout << root;
}

int main(){
    cin >> n;
    
    for(int i = 0; i < n; i++){
        char p, l, r;
        cin >> p >> l >> r;
        tree[p - 'A'][0] = l;
        tree[p - 'A'][1] = r;
    }
    preorder('A');
    cout << endl;
    inorder('A');
    cout << endl;
    postorder('A');
}