[SWEA 1231 : JAVA] 중위순회 / 완전 이진 트리

문제

---

SWEA의 문제를 무단 복제 하는 것은 금지라 링크를 남긴다.

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV140YnqAIECFAYD&categoryId=AV140YnqAIECFAYD&categoryType=CODE&&&

SW Expert Academy

 

요약하면, 입력으로 노드 값을 받아 완전 이진 트리를 구성하여, 중위 순회를 하여 출력하는 문제다.

 

 

 

풀이

---

완전 이진 트리의 값이 차례대로 입력으로 들어오기 때문에 인덱스 그대로 배열에 담아 inorder() 메서드로 간단히 풀 수도 있었겠지만,

BinaryTree 클래스를 한 번 만들어보고 싶었다. 완전 이진 트리를 구성할 때 차례대로 세팅되는 노드 값이 주어지면 최초에 세팅된 트리를 만드는건 어렵지 않다. 다만, 완전 이진 트리가 구성된 이후에 값을 하나씩 insert해주는걸 만들고 싶어서 몇 시간 고민해보았지만.....

답을 찾지 못했다. (혹시 아시는 분이 계시면 댓글 달아주세요.. 😭)

 

결론적으로, 완전 이진 트리를 구성하는 노드의 값이 차례대로 들어가있는 배열을 파라미터로 받아 삽입 연산을 수행했다.

 

 

 

코드

---

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

public class Solution {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int T;
    private static StringBuilder ans = new StringBuilder();

    public static void main(String[] args) throws IOException {
        while (T++ < 10) {
            ans.append("#").append(T).append(" ");

            BinaryTree<Character> tree = new BinaryTree<>();
            int N = Integer.parseInt(br.readLine());

            StringTokenizer st;
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                st.nextToken();
                sb.append(st.nextToken());
            }

            Character[] arr = sb.toString().chars().mapToObj(c -> (char) c).toArray(Character[]::new);
            tree.root = tree.insert(arr, tree.root, 0);
            tree.inorderTree(tree.root);
            ans.append("\n");
        }
        System.out.println(ans);
    }

    private static class BinaryTree<T> {

        private Node<T> root = null;

        public Node<T> insert(T[] arr, Node<T> root, int i) {
            if (i < arr.length) {
                root = new Node<>(arr[i]);
                root.leftChild = insert(arr, root.leftChild, 2 * i + 1);
                root.rightChild = insert(arr, root.rightChild, 2 * i + 2);
            }
            return root;
        }

        public void inorderTree(Node<T> root) {
            if (root != null) {
                inorderTree(root.leftChild);
                ans.append(root.data);
                inorderTree(root.rightChild);
            }
        }

        private static class Node<T> {
            private T data;
            private Node<T> leftChild;
            private Node<T> rightChild;

            public Node(T data) {
                this.data = data;
                leftChild = null;
                rightChild = null;
            }
        }
    }
}