5. [백준] 1991번 트리 순회 - 이진 트리 Binary Tree(3)

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

1991번: 트리 순회

---

        Remind Binary Tree

• Binary Tree란 무엇인가?
  각 부모 노드가 최대 두 개의 자식 노드를 가지는 자료구조
  각각의 자식 노드는 왼쪽, 오른쪽이라고 명시하기 때문에, 일반적인 트리 구조가 아님!
• 전위 순회, 후위 순회, 중위 순회
  루트 노드부터 모든 노드를 어떻게 방문하는 순서
  (부모(1) - 왼쪽 자식(2) - 오른쪽 자식(3))
  전위 순회 : (1) - (2) - (3)
  중위 순회 : (2) - (1) - (3)
  후위 순회 : (2) - (3) - (1)

---

     문제

     문제 풀이

• 전형적인 Binary Tree 구현 문제이다.
• 자바의 경우, linked list를 구현했을 때처럼 노드 클라스를 만드는데, link하는 노드가 left 와 right 두 개인 점이 다르다.
• 순회는 모두 재귀로 풀면 된다.
  전위의 경우, 부모를 출력하고 - 왼쪽 자식 - 오른쪽 자식을 방문하면 되는데, 이를 재귀적으로 왼쪽 자식의 서브 트리를 재귀적으로 불러 null일 때까지 호출하면 된다.
  후위의 경우, 왼쪽 자식, 오른쪽 자식, 부모 순으로 재귀하면 된다.
  중위의 경우, 왼쪽 자식, 부모, 오른쪽 자식 순으로 재쉬하면 된다.
• 푼 방법
  1. 노드를 구현한다.
  2. 루트 노드를 설정한다.(항상 A가 루트가 된다는 거 잘 읽고 확인하기)
  3. 노드에 값을 넣고 자식 노드와 연결한다.
  4. 순회 함수를 호출한다.

---

        JAVA code

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

public class baekjoon1991 {

    static class Node {
        char value;
        Node left;
        Node right;

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

    static Node head = new Node('A', null, null);

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

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

            char root = st.nextToken().charAt(0);
            char left = st.nextToken().charAt(0);
            char right = st.nextToken().charAt(0);

            insertNode(head, root, left, right);
        }
        preorder(head);
        System.out.println();
        inorder(head);
        System.out.println();
        postorder(head);
    }

    public static void insertNode(Node temp, char root, char left, char right) {
        if (temp.value == root) {
            temp.left = (left == '.' ? null : new Node(left, null, null));
            temp.right = (right == '.' ? null : new Node(right, null, null));
        } else {
            if (temp.left != null)
                insertNode(temp.left, root, left, right);
            if (temp.right != null)
                insertNode(temp.right, root, left, right);
        }
    }

    public static void preorder(Node node) {
        if (node == null)
            return;
        System.out.print(node.value);
        preorder(node.left);
        preorder(node.right);
    }

    public static void inorder(Node node) {
        if (node == null)
            return;
        inorder(node.left);
        System.out.print(node.value);
        inorder(node.right);
    }

    public static void postorder(Node node) {
        if (node == null)
            return;
        postorder(node.left);
        postorder(node.right);
        System.out.print(node.value);
    }
}