[데이터 구조] - 정렬 알고리즘 - 1.3, 이 진 트 리 정렬

[데이터 구조] - 정렬 알고리즘 - 1.2, 이 진 트 리 정렬
1. 먼저 위 키 의 그림: 이 진 트 리 정렬 위 키
그림 1, 이 진 트 리 정렬
묘사
이 진 트 리 (영어: Binary Search Tree) 는 이 진 트 리, 질서 있 는 이 진 트 리 (영어: ordered binary tree) 라 고도 부 르 며 이 진 트 리 (영어: sorted binary tree) 를 정렬 합 니 다. 빈 트 리 나 다음 과 같은 성질 을 가 진 이 진 이 진 트 리 를 말 합 니 다.
임의의 노드 의 왼쪽 나무 가 비어 있 지 않 으 면 왼쪽 나무 에 있 는 모든 노드 의 값 이 뿌리 노드 의 값 보다 작 거나 같 습 니 다.
만약 에 임의의 노드 의 오른쪽 나무 가 비어 있 지 않 으 면 오른쪽 나무 에 있 는 모든 노드 의 값 은 그의 뿌리 노드 의 값 보다 크다.
임의의 노드 의 왼쪽, 오른쪽 트 리 도 각각 두 갈래 로 나 무 를 찾는다.
키 가 같은 노드 가 없습니다.이 진 트 리 는 다른 데이터 구조 에 비해 검색, 삽입 시간 이 복잡 하 다 는 장점 이 있다.O (log n) 입 니 다.이 진 트 리 는 기본 적 인 데이터 구조 로 더욱 추상 적 인 데이터 구 조 를 구축 하 는 데 사용 된다. 예 를 들 어 집합, multiset, 관련 배열 등 이다.
이 진 트 리 b 에서 x 를 찾 는 과정 은 다음 과 같 습 니 다.
b 가 빈 나무 라면 검색 에 실 패 했 습 니 다. 그렇지 않 으 면: x 가 b 와 같은 루트 노드 의 데이터 필드 값 을 찾 으 면 성공 합 니 다.그렇지 않 으 면: 만약 x 가 b 보다 작은 루트 노드 의 데이터 필드 의 값 이 라면 왼쪽 하위 트 리 를 검색 합 니 다.그렇지 않 으 면: 오른쪽 트 리 찾기.
자바 프로그램

public class OrderTree {
    public static void main(String[] args) {
        /**
         *                        ***4***
         *                        *2***6*
         *                        1*3*5*7
         * 
         */
        int[] a = {4,2,1,3,6,5,7,8,9};
        BTree root = new BTree();
        createOrder(a, root);
        System.out.println("
pre order:");
        preOrder(root);
        System.out.println("
mid order:");
        midOrder(root);
        System.out.println("
last order:");
        lastOrder(root);
        List<Point> points = new ArrayList<Point>();
        //  tree        
        int floors = totalfloor(root);
        System.out.println("
floors:"+floors);
        printTree(root, points, 0, -1,floors);
         
        //     row,col             
        Collections.sort(points);
        //     5        （         ），  data==-1     *
        int row = 0;
        StringBuilder sb = new StringBuilder();
        int totalLength = 1*(squat(2, floors)-1);
        for(Point p : points){
            if(row == p.row){
                sb.append(printTimes("*",1*p.col-sb.length()));
                sb.append(printWidth(""+p.data, 1));
            }else{
                if(sb.length()< totalLength){
                    sb.append(printTimes("*", totalLength-sb.length()));
                }
                System.out.println(sb.toString());
                sb = new StringBuilder();
                row++;
                sb.append(printTimes("*",1*p.col-sb.length()));
                sb.append(printWidth(""+p.data, 1));
            }
        }
        if(sb.length()< totalLength){
            sb.append(printTimes("*", totalLength-sb.length()));
        }
        System.out.println(sb.toString());
         
         
    }
    static int totalfloor(BTree root){
        if(root == null)return 0;
        return internalLoop(root, 0);
    }
    static int internalLoop(BTree root,int floor){
        if(root != null){
            floor++;
            int left = internalLoop(root.left, floor);
            int right = internalLoop(root.right, floor);
            return Math.max(left, right);
        }
             
        else return floor;
    }
    static String printTimes(String s,int time){
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<time;i++){
            sb.append(s);
        }
        return sb.toString();
    }
    static String printWidth(String s ,int width){
        if(s == null ){
            return printTimes(" ", width);
        }else{
            if(s.length() < width){
                return new StringBuilder(s).append(printTimes("*", width-s.length())).toString();
            }else{
                return s.substring(0,width);
            }
        }
    }
    static class Point implements Comparable<Point>{
        public Point(int row,int col,int data){
            this.row = row;
            this.col = col;
            this.data = data;
        }
        int row = 0;
        int col = 0;
        int data = -1;
        @Override
        public int compareTo(Point o) {
            if(this.row == o.row){
                if(col == o.col)
                    return 0;
                else if(col < o.col){
                    return -1;
                }else{
                    return 1;
                }
            }else if(row < o.row){
                return -1;
            }else{
                return 1;
            }
        }
         
    }
    static void printTree(BTree root,List<Point> points,int row,int col,int floors){
        if(root != null){
            int inter = squat(2, floors-1)-1;
            if(col == -1){
                col = inter;
            }
            /**
             *                           ***0***
             *                           *0***0*
             *                           0*0*0*0
             * 
             */
            points.add(new Point(row, col, root.data));
            printTree(root.left,points,row+1, col - ((inter-1)/2)-1,floors -1);
            printTree(root.right,points,row+1,col + (inter-1)/2+1 ,floors -1);
        }
    }
    static int squat(int s,int b){
        if(b == 0) return 1;
        int result = 1;
        for(int i=0;i<b ;i++){
            result *=s;
        }
        return result;
    }
    static void preOrder(BTree root){
        if(root == null) {
            return ;
        }
        System.out.print("-"+root.data);
        preOrder(root.left);
        preOrder(root.right);
    }
    static void midOrder(BTree root){
        if(root == null) return ;
        midOrder(root.left);
        System.out.print("-"+root.data);
        midOrder(root.right);
    }
    static void lastOrder(BTree root){
        if(root == null) return ;
        lastOrder(root.left);
        lastOrder(root.right);
        System.out.print("-"+root.data);
    }
     
     
    //    ，   ，      
    static void createOrder(int[] a,BTree root){
         
        if(a == null || a.length == 0) return ;
        for(int i=0;i<a.length;i++){
            if(i==0){
                root.data = a[i];
            }else{
                BTree leaf = new BTree();
                leaf.data = a[i];
                insert(root,leaf);
            }
        }
    }
    static void insert(BTree root,BTree leaf){
        if(root.data == leaf.data){ // ==    
            if(root.left == null){
                root.left = leaf;
            }else{
                insert(root.left,leaf);
            }
        }else if(root.data > leaf.data){ // >    
            if(root.left == null){
                root.left = leaf;
            }else{
                insert(root.left,leaf);
            }
        }else{                          // <    
            if(root.right == null){
                root.right = leaf;
            }else{
                insert(root.right,leaf);
            }
        }
    }
     
    static class BTree{
        BTree left;
        BTree right;
        int data;
    }
}

모음 집: 자바 이 진 트 리 의 실현 (이 건 쉽게 알 아 볼 수 있다);
자바 기초 복습 노트 10 데이터 구조 - 정렬 이 진 트 리