트리 순회하기

트리의를 순회하는 방법은 3가지가 있다

1. 전위 순회 : Root -> Left -> Right

2. 중위 순회 : Left -> Root -> Right

3. 후위 순회 : Left -> Root -> Right

외우는 방법

전위순회는 root 가 앞에

중위는 root 가 중간에

후위는 root 가 뒤에

전위순회한 결과 : ABDCEFG

중위순회한 결과 : DBAECFG

후위순회한 결과 : DBEGFCA

 

# 문제

1991번 : 트리 순회하기

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

설명 : 단순히 트리를 순회하는 코드를 작성하는 문제이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

// Node 클래스: 트리의 각 노드를 정의
class Node {
    String name; // 노드 이름
    Node left;   // 왼쪽 자식 노드
    Node right;  // 오른쪽 자식 노드

    public Node(String name) {
        this.name = name;
    }
}

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 1. 트리의 노드 개수 입력
        int nodeCount = Integer.parseInt(br.readLine());

        // 2. 트리를 저장할 리스트 생성 (노드 이름은 'A', 'B', 'C' 등으로 초기화)
        List<Node> tree = new ArrayList<>();
        for (int i = 0; i < nodeCount; i++) {
            tree.add(new Node(String.valueOf((char) ('A' + i))));
        }

        // 3. 각 노드의 연결 정보 입력 및 트리 구성
        for (int i = 0; i < nodeCount; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String rootName = st.nextToken();   // 현재 루트 노드 이름
            String leftName = st.nextToken();  // 왼쪽 자식 노드 이름
            String rightName = st.nextToken(); // 오른쪽 자식 노드 이름

            // 현재 루트 노드를 가져옴
            Node rootNode = tree.get(rootName.charAt(0) - 'A');

            // 왼쪽 자식이 "."이 아니면 연결
            if (!leftName.equals(".")) {
                rootNode.left = tree.get(leftName.charAt(0) - 'A');
            }

            // 오른쪽 자식이 "."이 아니면 연결
            if (!rightName.equals(".")) {
                rootNode.right = tree.get(rightName.charAt(0) - 'A');
            }
        }

        // 4. 전위 순회, 중위 순회, 후위 순회 결과 출력
        System.out.println(preOrder(tree.get(0))); // 루트부터 시작
        System.out.println(inOrder(tree.get(0)));
        System.out.println(postOrder(tree.get(0)));
    }

    // 전위 순회 (Pre-order): 루트 → 왼쪽 → 오른쪽
    static String preOrder(Node currentNode) {
        if (currentNode == null) return ""; // 현재 노드가 null이면 종료
        return currentNode.name + preOrder(currentNode.left) + preOrder(currentNode.right);
    }

    // 중위 순회 (In-order): 왼쪽 → 루트 → 오른쪽
    static String inOrder(Node currentNode) {
        if (currentNode == null) return ""; // 현재 노드가 null이면 종료
        return inOrder(currentNode.left) + currentNode.name + inOrder(currentNode.right);
    }

    // 후위 순회 (Post-order): 왼쪽 → 오른쪽 → 루트
    static String postOrder(Node currentNode) {
        if (currentNode == null) return ""; // 현재 노드가 null이면 종료
        return postOrder(currentNode.left) + postOrder(currentNode.right) + currentNode.name;
    }
}