[테코테코 1.5 5-01] 백준 트리순회로 설명하는 트리 자료구조 & 전·중·후위 순회

1. 트리(Tree)란?

1-1. 왜 트리를 배우나?

• 계층적 구조를 표현하는 대표적인 자료구조이다.
• 파일/폴더 구조, HTML DOM, 조직도 등 실제로 많이 볼 수 있는 형태
• 코딩 테스트나 면접에서는 트리 순회나 이진 탐색 트리(BST) 가 출제된다.
• 데이터가 “부모-자식” 관계로 연결될 때, 굉장히 직관적으로 사용할 수 있다.

 

1-2. 시각적 예시

간단히 트리를 그림으로 표현한다면 아래와 같다.

   (A)  <-- 루트 노드
   / \  
 (B) (C)
 / \   \ 
(D)(E) (F)

• A는 루트, B는 왼 자식, C는 오른 자식
• B의 왼 자식(D), 오른 자식(E), C의 오른 자식(F)

부모 → 자식 관계가 명확해서, DFS(깊이 우선 탐색)나 BFS(너비 우선 탐색)을 직관적으로 적용할 수 있다.

 

 

2. 백준 1991 트리순회로 이해하는 전·중·후위 순회

2-1. 문제 내용

• 백준 1991 트리순회 (트리 순회)
• N개의 노드(알파벳 대문자)가 주어지고, 각 노드의 왼쪽 자식/오른쪽 자식 정보가 주어짐.
• 트리를 구성한 뒤, 전위 순회, 중위 순회, 후위 순회 결과를 출력

예시 입력

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

• . 은 자식이 없다는 의미
• A의 왼쪽 자식 = B, 오른쪽 자식 = C
• B의 왼쪽 자식 = D, 오른쪽 없음
• C의 왼쪽 자식 = E, 오른쪽 자식 = F … 이런 식으로 트리를 구성

 

2-2. 트리 구조

    A
   / \
  B   C
 /   / \
D   E   F
         \
          G

• A: 루트
• B: 왼쪽 서브트리의 루트, D가 B의 왼쪽 자식
• C: 오른쪽 서브트리의 루트, E와 F가 각각 왼/오른쪽 자식, F의 오른쪽 자식이 G

 

3. 전위·중위·후위 순회

트리 순회 방법은 전위(Preorder), 중위(Inorder), 후위(Postorder) 세 가지가 대표적이다.

1. 전위(Preorder): 루트 → 왼쪽 → 오른쪽
   • 제일 먼저 현재 노드를 방문
   • 트리 복제 등에 자주 쓰임
2. 중위(Inorder): 왼쪽 → 루트 → 오른쪽
   • 이진 탐색 트리(BST)에서 오름차순 정렬 결과를 얻을 때 유용
3. 후위(Postorder): 왼쪽 → 오른쪽 → 루트
   • 자식을 다 처리한 뒤 부모를 방문 → 트리 삭제 시, 혹은 후위 표기법(RPN) 계산 시 편리

💡 중위 순회는 왜 이진탐색트리에서 오름차순 정렬 결과를 얻을 때 자주 활용될까?

이진 탐색 트리(Binary Search Tree, 이하 BST)의 중위(Inorder) 순회가 오름차순 정렬 순서를 얻기 위해 자주 활용되는 이유는 다음과 같은 BST 고유의 성질 때문이다.

BST(Binray Search Tree) 성질

BST에서는 각 노드의 왼쪽 서브트리가 루트 노드보다 작은 값들로만, 그리고 오른쪽 서브트리가 루트 노드보다 큰 값들로만 구성된다.

(왼쪽 서브트리) < (루트 노드) < (오른쪽 서브트리)

위 규칙이 트리의 모든 노드에 대해 재귀적으로 적용된다.

중위 순회(Inorder): Left → Root → Right

중위 순회 방법에 따라 아래와 같은 순서로 노드를 방문한다.

1. 왼쪽 서브트리를 중위 순회
2. 루트 노드를 방문(출력)
3. 오른쪽 서브트리를 중위 순회

BST의 왼쪽 하위 트리는 항상 루트보다 작은 값들, 오른쪽 하위 트리는 항상 루트보다 큰 값들이라는 사실과 결합하면,
왼쪽의 모든 값 → 현재(루트) 값 → 오른쪽의 모든 값 순으로 방문하게 되어 결과적으로 값은 오름차순이 된다.

 

4. 백준 1991 트리순회 코드 구현

 

트리 노드를 간단히 클래스로 표현하거나, HashMap<Character, Node> 형태로 루트/왼쪽/오른쪽 정보를 저장할 수 있다.

구현 시 유의할 점

• 입력에서 '.' 문자가 나오면 자식이 없다는 의미
• 전위/중위/후위 함수를 각각 재귀로 작성

import java.io.*;
import java.util.*;

public class Main {

    // 트리 노드 정보를 저장할 map
    static Map<Character, Node> tree = new HashMap<>();

    public static void main(String[] args) throws IOException {
        // 입력 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine().trim());

        // 입력값으로 트리 구성
        for (int i = 0; i < N; i++) {
            String[] input = br.readLine().split(" ");
            char root = input[0].charAt(0);
            char left = input[1].charAt(0);
            char right = input[2].charAt(0);

            // HashMap에 각 노드를 key로 저장
            // key='A' → Node(val='A', left=?, right=?)
            tree.putIfAbsent(root, new Node(root));
            // 루트 노드 지정
            Node rootNode = tree.get(root);

            // 왼쪽 자식이 있을 시
            if (left != '.') {
                // HashMap에 각 노드를 key로 저장
                tree.putIfAbsent(left, new Node(left));
                // 왼쪽 자식 노드 지정
                rootNode.left = tree.get(left);
            }

            // 오른쪽 자식이 있을 시
            if (right != '.') {
                // HashMap에 각 노드를 key로 저장
                tree.putIfAbsent(right, new Node(right));
                // 오른쪽 자식 노드 지정
                rootNode.right = tree.get(right);
            }
        }

        // 트리의 루트를 항상 'A'라고 가정 시
        Node rootA = tree.get('A');

        // 전위 순회
        preorder(rootA);
        System.out.println();

        // 중위 순회
        inorder(rootA);
        System.out.println();

        // 후위 순회
        postorder(rootA);
        System.out.println();
    }

    // 노드 클래스 정의
    static class Node {
        char val;
        Node left, right;

        Node(char c) { this.val = c; }
    }

    // 순회는 모두 재귀 호출 이용
    // 전위 순회: Root → Left → Right
    static void preorder(Node node) {
        if (node == null) return;
        // Root : 출력
        System.out.print(node.val);
        // Left
        preorder(node.left);
        // Rigth
        preorder(node.right);
    }

    // 중위 순회: Left → Root → Right
    static void inorder(Node node) {
        if (node == null) return;
        // Left
        inorder(node.left);
        // Root : 출력
        System.out.print(node.val);
        // Right
        inorder(node.right);
    }

    // 후위 순회: Left → Right → Root
    static void postorder(Node node) {
        if (node == null) return;
        // Left
        postorder(node.left);
        // Right
        postorder(node.right);
        // Roodt : 출력
        System.out.print(node.val);
    }
}

 

 

5. 결과

• 전위: ABDCEFG …
• 중위: DBAECFG …
• 후위: DBEGFCA …

---

6. 정리

1. 트리: 루트에서 시작해 부모-자식으로 뻗어나가는 계층 구조
2. 트리 순회: 전위/중위/후위 모두 DFS, 방문 순서가 조금씩 다름

추가 참고 자료

• 트리 자료구조 by 동빈 나