[백준] 1991번 : 트리 순회

트리 순회

---

풀이 방법

이번 문제는 이진 트리의 3가지 순회 방법을 구현하는 문제였다.

트리의 기본 지식은 알기 때문에 설명은 생략했다.
이진 트리는 '모든 노드의 최대 차수를 2로 제한한 것' 이다.

전위, 중위, 후위 순회의 특징만 안다면 쉽게 구현할 수 있다.

잘 정리된 블로그를 참고해 잊었던 기억을 빠르게 되찾을 수 있었다.!! (감사합니다ㅠㅠ)

• 추가로 블로그를 참고하다가 제너릭에 대해 다시 공부하게 되어서 이번 문제에 적용시켜 봤다. 열심히 써먹어서 익숙해지자..

참고 블로그 : https://st-lab.tistory.com/300#%ED%81%B4%EB%9E%98%EC%8A%A4

느낀 점

이번 문제는 트리의 구조를 구성하고, 그저 순회 순서만 구현하면 되기 때문에 구현이 상당히 수월했다.

하지만, 워낙 오래전에 배운 것이라.. 기억이 가물가물해서 다시 지식을 습득하는데 조금 걸렸다.

다음에 트리를 구현할 때는 막힘 없이 구현하는 것을 목표로 하자!

---

소스 코드

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

class Node<E> {
    E value;
    Node<E> left;
    Node<E> right;
    public Node(E value) {
        this.value = value;
    }
}
class Tree<E> {
    public Node<E> root;
    public void createNode(E value, E left, E right){
        if(root == null){
            root = new Node<>(value);
            root.left = left.equals('.') ? null : new Node<>(left);
            root.right = right.equals('.') ? null : new Node<>(right);
        } else {
            searchNode(root, value, left, right);
        }
    }
    private void searchNode(Node<E> root, E value, E left, E right) {
        if(root == null){
            return;
        } else if(root.value == value) {
            root.left = left.equals('.') ? null : new Node<>(left);
            root.right = right.equals('.') ? null : new Node<>(right);
        } else {
            searchNode(root.left, value, left, right);
            searchNode(root.right, value, left, right);
        }
    }
    public void preOrder(Node<E> node){
        if(node != null){
            System.out.print(node.value);
            if(node.left != null) preOrder(node.left);
            if(node.right != null) preOrder(node.right);
        }
    }
    public void inOrder(Node<E> node){
        if(node != null){
            if(node.left != null) inOrder(node.left);
            System.out.print(node.value);
            if(node.right != null) inOrder(node.right);
        }
    }
    public void postOrder(Node<E> node){
        if(node != null){
            if(node.left != null) postOrder(node.left);
            if(node.right != null) postOrder(node.right);
            System.out.print(node.value);
        }
    }
}
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        Tree<Character> tree = new Tree<>();

        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine(), " ");
            char root = st.nextToken().charAt(0);
            char left = st.nextToken().charAt(0);
            char right = st.nextToken().charAt(0);
            tree.createNode(root,left,right);
        }

        tree.preOrder(tree.root);
        System.out.println();

        tree.inOrder(tree.root);
        System.out.println();

        tree.postOrder(tree.root);
        System.out.println();
    }
}