[백준] 1991번 : 트리 순회 - 자바[Java]

1991번: 트리 순회

풀이

<트리 자료구조 생성>

Node 클래스를 생성하고, 클래스 내에 String value, Node left, Node right 인스턴스 변수를 생성하여 각각 노드 값, 왼쪽 자식 노드, 오른쪽 자식 노드를 저장한다.

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

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

문제에서 "항상 A가 루트 노드가 된다"고 나와있기 때문에 static 변수로 루트 노드 Node root = new Node("A", null, null)을 생성한다.

    static Node root = new Node("A", null, null); //트리의 루트 노드

각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드를 입력받을 때 insertNode() 함수를 호출하여 올바른 위치에 노드를 삽입한다.

    static void insertNode(Node node, String parent, String left, String right) {
        if (node.value.equals(parent)) {
            node.left = left.equals(".") ? null : new Node(left, null, null);
            node.right = right.equals(".") ? null : new Node(right, null, null);
        }
        else {
            if (node.left != null)
                insertNode(node.left, parent, left, right);
            if (node.right != null)
                insertNode(node.right, parent, left, right);
        }
    }

 

그 후 전위 순회, 중위 순회, 후위 순회를 한 결과를 출력하면 된다.

 

코드

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

public class Main {

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

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

    static Node root = new Node("A", null, null); //트리의 루트 노드
    static StringBuilder sb = new StringBuilder();  //출력 결과

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        StringTokenizer st;

        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            String parent = st.nextToken();
            String left = st.nextToken();
            String right = st.nextToken();

            insertNode(root, parent, left, right);
        }

        preOrder(root); //전위 순회
        sb.append("\n");

        inOrder(root); //중위 순회
        sb.append("\n");

        postOrder(root); //후위 순회
        sb.append("\n");
        
        System.out.println(sb);
    }

    static void insertNode(Node node, String parent, String left, String right) {
        if (node.value.equals(parent)) {
            node.left = left.equals(".") ? null : new Node(left, null, null);
            node.right = right.equals(".") ? null : new Node(right, null, null);
        }
        else {
            if (node.left != null)
                insertNode(node.left, parent, left, right);
            if (node.right != null)
                insertNode(node.right, parent, left, right);
        }
    }

    static void preOrder (Node node) {
        if (node == null) return;

        sb.append(node.value);
        preOrder(node.left);
        preOrder(node.right);
    }

    static void inOrder (Node node) {
        if (node == null) return;

        inOrder(node.left);
        sb.append(node.value);
        inOrder(node.right);
    }

    static void postOrder (Node node) {
        if (node == null) return;

        postOrder(node.left);
        postOrder(node.right);
        sb.append(node.value);
    }

}

 

Reference

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