728x90

[문제]

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

  • 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
  • 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
  • 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

 

[문제 풀이]

전위 순회 (루트, 왼쪽, 오른쪽) 로 입력이 들어올때 노드를 생성하며 tree 구조로 만들어 주었다.

만들어진 tree 구조에서 후위 순회를 하며 결과를 하나씩 출력해 주었다.

 

 

[코드]

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

public class Main {

    static Node root;
    static StringBuilder sb = new StringBuilder();

    static int stoi(String s) {
        return Integer.parseInt(s);
    }

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

        // 노드 생성 트리 생성
        String n;
        while(true) {
            n = br.readLine();
            if (n == null || n.equals("")) break;
            Node node = new Node(stoi(n));
            connectNode(root, node);
        }

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

    static void postOrder(Node node) {
        if (node.left != null) postOrder(node.left);
        if (node.right != null) postOrder(node.right);
        sb.append(node.num).append("\n");
    }

    static void connectNode(Node cur, Node next) {
        if (next.num < cur.num) {
            if (cur.left != null) {
                connectNode(cur.left, next);
            } else {
                cur.left = next;
            }
        } else {
            if (cur.right != null) {
                connectNode(cur.right, next);
            } else {
                cur.right = next;
            }
        }
    }

    static class Node {
        int num;
        Node left;
        Node right;

        Node(int num) {
            this.num = num;
        }
    }
}

[실행 결과]

이와 같이 나온다.

728x90

'Algorithm > Baekjoon' 카테고리의 다른 글

[BOJ] 2606 바이러스 - Java  (0) 2021.07.26
[BOJ] 1991 트리 순회 - Java  (0) 2021.07.16
[BOJ] 1068 트리 - Java  (0) 2021.07.14
[BOJ] 11279 최대 힙 - Java  (0) 2021.07.14
[BOJ] 1927 최소 힙 - Java  (0) 2021.07.14

+ Recent posts