백준 1991번 [트리 순회](C++) -yes6686- 티스토리

백준 문제 풀이: 1991 [트리 순회]

---

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

문제 설명:

이진 트리에서 다음 세 가지 순회 방법을 구현하는 문제입니다.

• 전위 순회 (Preorder Traversal): 루트 → 왼쪽 자식 → 오른쪽 자식
• 중위 순회 (Inorder Traversal): 왼쪽 자식 → 루트 → 오른쪽 자식
• 후위 순회 (Postorder Traversal): 왼쪽 자식 → 오른쪽 자식 → 루트

주어진 트리의 구조를 기반으로 각 순회 방법에 따른 결과를 출력합니다.

입력:

• 첫 번째 줄에 노드의 개수 n이 주어집니다. (1 ≤ n ≤ 26)
• 다음 n개의 줄에는 각각 루트 노드, 왼쪽 자식 노드, 오른쪽 자식 노드가 주어집니다. 자식이 없는 경우 '.'으로 표시됩니다.

출력:

• 세 줄에 걸쳐 각각 전위 순회, 중위 순회, 후위 순회의 결과를 출력합니다.

---

문제 해결 코드

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

// 트리 구조를 저장하는 배열
int tree[26][2]; // [노드][0]: 왼쪽 자식, [노드][1]: 오른쪽 자식

// 전위 순회 (Preorder)
void preorder(int node) {
    if (node == -1) return; // 자식 노드가 없는 경우
    cout << char(node + 'A'); // 현재 노드 출력
    preorder(tree[node][0]); // 왼쪽 자식 방문
    preorder(tree[node][1]); // 오른쪽 자식 방문
}

// 중위 순회 (Inorder)
void inorder(int node) {
    if (node == -1) return;
    inorder(tree[node][0]); // 왼쪽 자식 방문
    cout << char(node + 'A'); // 현재 노드 출력
    inorder(tree[node][1]); // 오른쪽 자식 방문
}

// 후위 순회 (Postorder)
void postorder(int node) {
    if (node == -1) return;
    postorder(tree[node][0]); // 왼쪽 자식 방문
    postorder(tree[node][1]); // 오른쪽 자식 방문
    cout << char(node + 'A'); // 현재 노드 출력
}

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        char root, left, right;
        cin >> root >> left >> right;

        int rootIdx = root - 'A';
        tree[rootIdx][0] = (left == '.') ? -1 : (left - 'A'); // 왼쪽 자식 노드
        tree[rootIdx][1] = (right == '.') ? -1 : (right - 'A'); // 오른쪽 자식 노드
    }

    preorder(0); // 루트 노드는 'A'로 시작
    cout << '\n';
    inorder(0);
    cout << '\n';
    postorder(0);
    cout << '\n';

    return 0;
}

예제

입력:
7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

출력:
ABDCEFG
DBAECFG
DBEGFCA

입력:
3
A B .
B C .

출력:
ABC
CBA
CBA

---

코드 설명

• 트리 저장: 각 노드를 배열 tree에 저장하며, '.'은 -1로 처리합니다.
• 순회 구현: 전위, 중위, 후위 순회는 재귀적으로 구현됩니다.
• 노드 인덱스: 노드 이름('A'-'Z')은 0부터 25까지의 인덱스로 변환됩니다.

시간 복잡도

• 각 노드는 한 번만 방문되므로 각 순회의 시간 복잡도는 O(n)입니다.
• 전체 시간 복잡도: O(n)

---

결과

코드는 입력된 트리를 정확히 표현하고, 세 가지 순회 방법으로 결과를 출력합니다. 입력 크기가 작으므로 O(n)의 시간 복잡도로 충분히 효율적입니다.

다른 테스트 사례나 개선 사항이 있다면 댓글로 공유 부탁드립니다!