[JAVA] 백준 1991번 : 트리 순회

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

1991번: 트리 순회

---

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

public class Main {
    static int N;
    static StringBuilder sb = new StringBuilder();
    static Node root = new Node('A', null, null);
    private static class Node {
        char mid; Node left; Node right;

        Node(char mid, Node left, Node right) {
            this.mid = mid;
            this.left = left;
            this.right = right;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        while (N-- > 0) {
            String[] input = br.readLine().split(" ");
            char mid = input[0].charAt(0);
            char left = input[1].charAt(0);
            char right = input[2].charAt(0);
            setTree(root, mid, left, right);
        }
        preOrder(root);
        sb.append("\n");
        inOrder(root);
        sb.append("\n");
        postOrder(root);
        System.out.print(sb);
    }

    //루트 - 왼쪽 - 오른쪽(있으면 출력) 없다면 왼쪽, 왼쪽 없으면 오른쪽 타고 내려감
    private static void preOrder(Node now) {
        if(now == null) return;
        sb.append(now.mid);
        preOrder(now.left);
        preOrder(now.right);
    }
    //왼쪽 - 루트 - 오른족
    private static void inOrder(Node now) {
        if(now == null) return;
        inOrder(now.left);
        sb.append(now.mid);
        inOrder(now.right);
    }
    //왼쪽 - 오른쪽 - 루트
    private static void postOrder(Node now) {
        if (now == null) return;
        postOrder(now.left);
        postOrder(now.right);
        sb.append(now.mid);
    }

    private static void setTree(Node now, char mid, char left, char right) {
        if (now.mid == mid) {
            now.left = left == '.' ? null : new Node(left, null, null);
            now.right = right == '.' ? null : new Node(right, null, null);
            return;
        }
        if(now.left != null)
            setTree(now.left, mid, left, right);
        if (now.right != null)
            setTree(now.right, mid, left, right);
    }
}

💡 트리,  재귀

풀이

💡 트리를 구현하기 위해 Node 클래스 정의함
    - 필드로 Node형 변수 2개(왼쪽, 오른쪽)가 존재하고, 거기 왼쪽, 오른쪽 자식 노드 정보를 저장하는 객체
    - 처음에 root 노드를 만들고, 주어지는 입력을 바탕으로 계속 이어주는 방식

• 트리를 구성하는 과정에서도 재귀 함수를 활용한다. 입력값으로 주어진 mid 값과 현재 보고있는 노드의 mid가 동일하면 해당 노드에 left, right 노드를 붙여준다
  • 이때 left, right값을 mid로 하는 노드를 생성해 연결해주는 방식이다. 
  • 단, left, right 값이 "."(null) 인지 아닌지 체크한다.
  • mid값이 동일하지 않다면, 왼쪽/오른쪽 자식 노드로 각각 탐색을 시작해 붙여준다
• 전위/중위/후위 탐색에서 중요한 것은 출력은 무조건 mid값만 한다는 것 => 얘를 토대로 재귀함수로 탐색
  • 왼쪽/오른쪽 자식노드들도 결국 본인 값을 mid로 하는 노드로 연결되어 있기 때문
  • null인 경우 탈출하는 조건이 필수적이다.

---

탐색 문제 자주 풀었었는데.. 안푸니 다시 감이 떨어졌다ㅠ 객체를 사용해서 풀이하는 방법에 주의할 것

+ 재귀 용법으로 트리 저장하는 방법 숙지