문제 // 자료구조 // 트리(Tree) // 최소높이 이진탐색트리 // toJava

/**
 * [최소트리]
 *  오름차순으로 정렬된 배열이 있고,
 *  이 배열의 원소는 정수이며 중복된 값이 없을때,
 *  높이가 최소가 되는 "이진탐색트리"를 만드는 알고리즘을 작성
 *
 * [풀이]
 *  => Tree를 직접만들어야할까요 ?
 *  => 높이가 최소이기 위해선 빈공간이 최소화 되야함
 * */
public class Q02 {

    /* main */
    public static void main(String[] args) {

        // [예상시나리오]
        // 4
        // 2   6
        // 1 3 5 7

        Tree tree = new Tree();
        int[] arr = new int[] {1, 2,3, 4, 5, 6, 7};
        minHeightTree(tree, arr, 0, arr.length-1);

        // @Test
        tree.print(); // 4 2 6 1 3 5 7
    }

    /* minHeightTree */
    static void minHeightTree(Tree tree, int[] arr, int start, int end) {
        int mid = (start+end)/2;
        tree.add(arr[mid]);
        if(start < mid) minHeightTree(tree, arr, start, mid-1);
        if(end > mid) minHeightTree(tree, arr, mid+1, end);
    }

    /* Node */
    static class Node<T> {
        T data;
        Node left;
        Node right;
        public Node(T data) {
            this.data = data;
        }
    }

    /* MyTree */
    static class Tree<T> {
        // == Filed ==
        Node<T> root;

        // == Constructor ==
        public Tree() { }

        // == add ==
        public void add(T data) {
            if(root != null) {
                Node node = root;
                Node newNode = new Node(data);
                while(true) {
                    if((int) node.data > (int) data) {
                        if(node.left == null) {
                            node.left = newNode;
                            break;
                        }
                        else node = node.left;
                    } else {
                        if(node.right == null) {
                            node.right = newNode;
                            break;
                        }
                        else node = node.right;
                    }
                }
            } else {
                root = new Node(data);
            }
        }

        // == remove ==
        public void remove() {
            // 생략
        }

        // == print - 너비우선탐색(큐) ==
        public void print() {
            Queue<Node> queue = new LinkedList();
            Node node = root;
            if(node.left != null) queue.add(node.left);
            if(node.right != null) queue.add(node.right);
            System.out.printf(node.data + " ");
            while (queue.size() != 0) {
                node = queue.remove();
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
                System.out.printf(node.data + " ");
            }
        }

    }
}