[백준] 1991번 트리순회 JAVA

 

분석

---

이 문제를 풀려면 트리 자료구조와 트리의 순환에 대해 알아야한다.

 

트리란?

가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조이다.

 

루트노드 :  부모가 없는 최상위 노드 (F)단말노드 : 자식이 없는 노드 (A,C,E,H)크기 : 트리에 포함 된 노드의 개수 (8)깊이 : 깊이 루트 노드부터의 거리높이 :  깊이 중 최댓값 (3)차수 : 각 노드의 간선 개수

 

* 트리의 크기가 N 일때, 전체 간선의 개수는 N-1 이다.

 

트리의 순회 

트리 자료구조에 포함 된 노드를 특정한 방법으로 한번씩 방문하는 방법이다.

 

대표적인 순회의 방법은 3가지가 있다.

1. 전위 순회 : 루트노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드 순으로 방문한다.

                       F B A D C E G I H

2. 중위 순회 :  왼쪽 자식노드 -> 루트 노드 -> 오른쪽 자식 노드

                       A B C D E F G H I

3. 후위 순회 :  왼쪽 자식노드 -> 오른쪽 자식 노드 -> 루트 노드

                       A C E D B H I G F

 

위의 방법을 적용해서 입력으로 노드간 연결 정보를 받은 뒤에 순회 결과를 출력하면 된다.

 

코드

---

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


public class Main {
    //최상위 루트 노드 생성
    static Node root = new Node('A',null,null);
    //트리에 들어갈 노드 클래스
    static class Node{
        char name;
        Node left;
        Node right;

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

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

        int num = Integer.parseInt(br.readLine());

        for(int i=0;i<num;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            InsertNode(root,st.nextToken().charAt(0),st.nextToken().charAt(0),st.nextToken().charAt(0));
        }

        preOrder(root);
        System.out.println();
        inOrder(root);
        System.out.println();
        postOrder(root);
    }

    private static void InsertNode(Node root, char value, char left, char right) {
        //현재 노드와 value 의 값이 같다면
        if(root.name == value){
            root.left = (left == '.' ? null : new Node(left,null,null));
            root.right = (right == '.' ? null : new Node(right,null,null));
        }

        else{
            //왼쪽 자식노드가 존재한다면 해당 노드 탐색 후 자식 노드 추가
            if(root.left != null) InsertNode(root.left,value,left,right);
            //오른쪽 자식노드가 존재한다면 해당 노드 탐색 후 자식 노드 추가
            if(root.right != null) InsertNode(root.right,value,left,right);
        }
    }
    //전위 순회
    static void preOrder(Node node){
        if(node == null) return;
        System.out.print(node.name+" ");
        preOrder(node.left);
        preOrder(node.right);
    }
    //중위 순회
    static void inOrder(Node node){
        if(node == null) return;
        inOrder(node.left);
        System.out.print(node.name+" ");
        inOrder(node.right);
    }
    //후위 순회
    static void postOrder(Node node){
        if(node == null) return;
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.name+" ");
    }


}

 

참고 사이트

https://www.youtube.com/watch?v=i5yHkP1jQmo&t=470s 

https://velog.io/@gandi0330/Java-%EB%B0%B1%EC%A4%80-%ED%8A%B8%EB%A6%AC-%EC%88%9C%ED%9A%8C-1991%EB%B2%88

[Java] 백준 / 트리 순회 / 1991번