[백준] 이진트리

안녕하세요!
이번 포스팅은 백준의 이진트리 문제 풀이를 적어보겠습니다.

---

문제

요약
이진 검색 트리를 전위 순회한 결과를 주면, 해당 트리의 후위 순회 결과를 출력합니다.

처음 생각한 방법

트리이기 때문에 트리와 노드를 클래스로 구현하는 방법을 생각했습니다.
전위 순회한 입력 값들을 트리에 데이터를 넣고, 후위 순회는 dfs 를 활용해 풀었습니다.

코드 설명

class Node {
    int data;
    Node left;
    Node right;

    public Node(int data) {
        this.data = data;
    }
}

Node 클래스입니다.
data 와 왼쪽 자식 노드를 나타내는 left , 오른쪽 자식 노드를 나타내는 right 를 멤버 변수로 사용합니다.

class Tree {
    Node root;

    public void addData(int data) {
        if (root == null) {
            root = new Node(data);
            return;
        }
        addData(root, data);
    }

    private void addData(Node node, int data) {
        if (node.data < data) {
            if (node.right == null) node.right = new Node(data);
            else addData(node.right, data);
        } else {
            if (node.left == null) node.left = new Node(data);
            else addData(node.left, data);
        }
    }
    
    // ...
}

Tree 클래스입니다.
멤버 변수는 root 노드 하나만 갖습니다.

데이터를 추가할 때, 만약 root 가 null 이라면 현재 들어온 데이터를 root 노드에 저장합니다.
root 가 null 이 아니라면 오버로딩된 addData() 메소드를 호출합니다.

그 메소드에서는 매개 변수로 넘어온 노드의 데이터가 삽입할 데이터보다 작다면 삽입은 오른쪽에 이루어져야하므로 매개 변수 노드의 오른쪽 자식 노드가 존재하는지 확인합니다.
만약 오른쪽 자식 노드가 있다면, addData() 를 재귀 호출하여 다시 비교합니다.
오른쪽 자식 노드가 없다면 현재 데이터를 자신의 오른쪽 자식 노드에 삽입합니다.

삽입할 데이터가 매개 변수 노드의 데이터보다 작다면 매개 변수 노드의 왼쪽 자식 노드가 존재하는지 확인합니다.
그 외 로직은 위와 동일합니다.

class Tree {
	// ...

    public void dfsByPostOrder() {
        dfsByPostOrder(root);
    }

    private void dfsByPostOrder(Node node) {
        if (node.left != null) dfsByPostOrder(node.left);
        if (node.right != null) dfsByPostOrder(node.right);
        System.out.println(node.data);
    }
}

Tree 클래스의 후위 순회 메소드입니다.

public 접근 제한자를 갖는 dfsByPostOrder() 메소드는 오버로딩된 메소드를 호출합니다.
root 부터 시작해서 현재 노드의 왼쪽 노드가 있다면 메소드를 재귀 호출합니다.
현재 노드의 오른쪽 노드가 있다면 메소드를 재귀 호출합니다.
왼쪽과 오른쪽 자식이 없거나 이미 탐색하고 나왔다면 자신의 데이터를 출력합니다.

public static void main(String[] args) throws IOException {
    Tree tree = new Tree();

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String input = "";

    while (true) {
        input = br.readLine();

        if (input == null) break;
        if (input.length() <= 0) break;

        tree.addData(Integer.parseInt(input));
    }

    tree.dfsByPostOrder();
}

메인 메소드는 위와 같습니다.
입력이 숫자를 정해주지 않으므로 while 반복문을 통해 라인을 계속 읽어오다가 읽어온 스트링이 null 이거나 길이가 0 이하라면 반복문을 탈출합니다.

전체 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        Tree tree = new Tree();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = "";

        while (true) {
            input = br.readLine();

            if (input == null) break;
            if (input.length() <= 0) break;

            tree.addData(Integer.parseInt(input));
        }

        tree.dfsByPostOrder();
    }
}

class Node {
    int data;
    Node left;
    Node right;

    public Node(int data) {
        this.data = data;
    }
}

class Tree {
    Node root;

    public void addData(int data) {
        if (root == null) {
            root = new Node(data);
            return;
        }
        addData(root, data);
    }

    private void addData(Node node, int data) {
        if (node.data < data) {
            if (node.right == null) node.right = new Node(data);
            else addData(node.right, data);
        } else {
            if (node.left == null) node.left = new Node(data);
            else addData(node.left, data);
        }
    }

    public void dfsByPostOrder() {
        dfsByPostOrder(root);
    }

    private void dfsByPostOrder(Node node) {
        if (node.left != null) dfsByPostOrder(node.left);
        if (node.right != null) dfsByPostOrder(node.right);
        System.out.println(node.data);
    }
}

---

마무리

이진 트리라는 알고리즘 제목답게, 이진 트리를 구조화하는 것에 많은 도움이 되었습니다.
난이도는 그렇게 어렵지 않았던 것 같습니다!

이번 포스팅도 읽어주셔서 감사합니다 :)