Complete Binary Search Tree - Java 실현

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:
The left subtree of a node contains only nodes with keys less than the node’s key. The right subtree of a node contains only nodes with keys greater than or equal to the node’s key. Both the left and right subtrees must also be binary search trees. A Complete Binary Tree (CBT) is a tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right.
Now given a sequence of distinct non-negative integer keys, a unique BST can be constructed if it is required that the tree must also be a CBT. You are supposed to output the level order traversal sequence of this BST.
Input Specification: Each input file contains one test case. For each case, the first line contains a positive integer N (≤1000). Then N distinct non-negative integer keys are given in the next line. All the numbers in a line are separated by a space and are no greater than 2000.
Output Specification: For each test case, print in one line the level order traversal sequence of the corresponding complete binary search tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.
Sample Input: 10 1 2 3 4 5 6 7 8 9 0
Sample Output: 6 3 8 1 5 7 9 0 2 4
생각:
4. 567917. 주어진 서열 에 따라 크기 에 따라 순 서 를 매기 고 완전 이 진 트 리 의 특징 에 따라 왼쪽 나무 개 수 를 확정 하고 오른쪽 나무 개 수 를 재 귀적 으로 완전 이 진 트 리 를 확인한다
4. 567917. 이 나 무 를 층 차 적 으로 옮 겨 다 니 며 결 과 를 얻 을 수 있다
코드 는 다음 과 같 습 니 다:

import java.io.BufferedReader;
import java.io.FileDescriptor;
import java.io.FileReader;
import java.util.Arrays;

public class Main {
    int num;
    
    public static void main(String[] args){
        BufferedReader br = new BufferedReader(new FileReader(FileDescriptor.in));
        Main self = new Main();
        try {
            int[] res = self.readInput(br);
            //           
            if(res.length == 1){
                System.out.print(res[0]);
            }else{
                CBTree head = new CBTree();
                head = self.buildTree(res, head);
                StringBuilder sb = self.orderTraversal(head);
                System.out.println(sb.substring(0,sb.length()-1));
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    //    (    ，         )
    public StringBuilder orderTraversal(CBTree head){
        Que que = new Que(num);
        que.addQue(head);
        StringBuilder sb = new StringBuilder();
        while (que.getLen() > 0){
            CBTree temp = que.leaveQue();
            sb.append(temp.data + " ");
            if (temp.left != null)
                 que.addQue(temp.left);
            if (temp.right != null)
                que.addQue(temp.right);
        }
        return sb;
    }

    //    
    public int[] readInput(BufferedReader br) throws Exception{
        num = Integer.parseInt(br.readLine().trim());
        int[] nodes = new int[num];
        String[] s = br.readLine().split(" ");
        for (int i = 0; i < num; i++) {
            nodes[i] = Integer.parseInt(s[i]);
        }
        //         (            )
        Arrays.sort(nodes);
        return nodes;
    }
    
    //            
    public CBTree buildTree(int[] nodes,CBTree head){
        //     
        int height = 0;
        for (int i = 0; Math.pow(2,i)-1< nodes.length; i++) {
            height = i + 1;
        }
        //        (height-1   )
        //     
        int leftNodes = nodes.length - (int) (Math.pow(2,height-1)-1);
        //        
        int leftTreeNodes = 0;
        if (leftNodes <= Math.pow(2,height-1)/2){
            leftTreeNodes = leftNodes + (int) ((Math.pow(2,height-1)-1)/2);
        }else {
            leftTreeNodes =(int) ((Math.pow(2,height)-1)/2);
        }
        //        
        int rightTreeNodes = nodes.length - 1 - leftTreeNodes;
        //     
        if (head == null){
            head = new CBTree(nodes[leftTreeNodes]);
        }else {
            head.data = nodes[leftTreeNodes];
        }

        //     
        if (leftTreeNodes >= 1){
            head.left = buildTree(Arrays.copyOfRange(nodes,0,leftTreeNodes),head.left);
        }
        //     
        if (rightTreeNodes >= 1){
            head.right = buildTree(Arrays.copyOfRange(nodes,leftTreeNodes+1,nodes.length),head.right);
        }
        return head;
    }

}
//     
class CBTree{
    int data;
    CBTree left;
    CBTree right;

    public CBTree() { }

    public CBTree(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
//  
class Que{
    private CBTree[] que;
    private int top;
    private int rear;

    public Que(int len) {
        this.que = new CBTree[len];
        this.top = -1;
        this.rear = -1;
    }

    public void addQue(CBTree node){
        que[++top] = node;
    }

    public CBTree leaveQue(){
        return que[++rear];
    }

    public int getLen(){
        return top-rear;
    }

}