[백준] 1991 트리 순회 - Java

 

문제 출저 

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

1991번: 트리 순회

 

 

 

문제 풀이

트리가 주어지고 이 트리의 전위 순회, 중위 순회, 후위 순회 했을 때 결과를 출력하는게 이 문제의 요구 사항이다. 

 

트리를 저장하기 위해 Node라는 클래스를 만들어 left, right를 저장했다.

이 노드의 연결 정보는 Map<String, Node> nodeMap 형태로 저장했다. 

순회를 구하는 방법은 재귀 함수를 사용했다. 

재귀 함수로 노드를 이동하고 적절한 시기에 StringBuilder sb에 노드를 넣어 순회를 구했다. 

 

start는 현재 탐색 중인 Node이다. 

전위 순회 : sb.append(start), 왼쪽 탐색, 오른쪽 탐색

중위 순회 : 왼쪽 탐색, sb.append(start), 오른쪽 탐색

후위 순회 : 왼쪽 탐색, 오른쪽 탐색, sb.append(start)

 

 

소스 코드

package baekjoon.backjoon9.day04;

/*
트리 순회
https://www.acmicpc.net/problem/1991
 */

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

public class B1991 {

    static int n;
    static Map<String, Node> nodeMap;
    static StringBuilder sb;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        nodeMap = new HashMap<>();

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            String start = st.nextToken();
            String left = st.nextToken();
            String right = st.nextToken();

            nodeMap.put(start, new Node(left, right));
        }

        sb = new StringBuilder();
        preOrder("A");
        sb.append("\n");
        inOrder("A");
        sb.append("\n");
        postOrder("A");


        System.out.println(sb);

    }

    public static void preOrder(String start) {

        if (start.equals(".")) {
            return;
        }
        Node node = nodeMap.get(start);

        sb.append(start);

        preOrder(node.left);
        preOrder(node.right);
    }

    public static void inOrder(String start) {
        if (start.equals(".")) {
            return;
        }

        Node node = nodeMap.get(start);

        inOrder(node.left);
        sb.append(start);
        inOrder(node.right);

    }

    public static void postOrder(String start) {
        if (start.equals(".")) {
            return;
        }

        Node node = nodeMap.get(start);


        postOrder(node.left);
        postOrder(node.right);
        sb.append(start);

    }


    public static class Node {
        String left;
        String right;

        Node(String left, String right) {
            this.left = left;
            this.right = right;
        }
    }
}