데이터 구조 (7): 2 분 검색 트 리

정의
1. 이분 수 트 리 는 이 진 트 리
2. 2 분 검색 트 리 의 각 노드 값 특성
   (1) 왼쪽 트 리 의 모든 노드 보다 큰 값   (2) 오른쪽 하위 트 리 의 모든 노드 보다 작은 값
3. 나무 한 그루 한 그루 도 2 분 검색 트 리
2. 코드 구현 기능
1. 원소 추가
2. 원소 옮 겨 다 니 기
(1) 앞 순 서 를 옮 겨 다 니 는 순서 가 실 현 됩 니 다.      -> 노드      ->  preOrder(node.left);       ->  preOrder(node.right);                 (2) 중간 순서 반복 실현:      ->  preOrder(node.left);       ->  노드      ->  preOrder(node.right);             특징: 노드 작은 것 부터 큰 것 까지
(3) 후 순서 반복 실현:
      ->  preOrder(node.left);       ->  preOrder(node.right);       ->  노드                     응용 장면: 노드 의 좌우 노드 를 먼저 처리 한 다음 에 노드 를 처리 해 야 합 니 다.예 를 들 어 2 분 검색 트 리 에 메모 리 를 방출 합 니 다.
(4) 앞 순 서 를 옮 겨 다 니 는 비 재 귀적 실현:
      Stack 창 고 를 빌려 실현 하 다
(5) 층 차 를 옮 겨 다 니 며 실현:
      queue 대기 열 을 빌려 실현 하 다
3. 검색
(1) 최소 값 검색
(2) 검색 최대 치
4. 삭제
(1) 최소 값 삭제
(2) 최대 값 삭제
(3) 임의의 노드 삭제
   -》 좌우 에 아이 가 있 는 노드 d 를 삭제 합 니 다.        우선, d 의 오른쪽 노드 의 최소 값 s = min (d - > right) 을 찾 습 니 다.        그리고 구축 s:                        s->right=delMin（d->right）                         s->left=d->left         마지막 으로 d 를 삭제 하고 s 를 사용 하면 루트 노드 d 를 교체 합 니 다.                
3. 자바 코드 구현

package com.DataStructures._06BinarySearchTree;

import java.util.*;

/**
 * Created by Administrator on 2018/12/16.
 */
public class BSTimprove> {

    //   
    private  class Node{
        public E e;
        public Node left,right;

        public Node(E e){
            this.e=e;
            left=null;
            right=null;
        }
    }

    //     
    private Node root;
    private int size;

    public BSTimprove(){
        root=null;
        size=0;
    }

    //***************************************************************
    //1.      
    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return size==0;
    }

    //***************************************************************
    //2.     

    /**
     * 2.1            
     * @param e
     */
    public  void add(E e){
//        if(root==null){
//            root=new Node(e);
//            size++;
//        }else {
//            add(root,e);
//        }
        root=add(root,e);
    }

    /**
     * 2.2  node             e，    
     *                
     * @param node
     * @param e
     * @return
     */
    private Node add(Node node,E e){

        if(node==null){
            size++;
            return new Node(e);
        }

        if(e.compareTo(node.e)<0){
            node.left= add(node.left,e);
        }else if(e.compareTo(node.e)>0){
            node.right=add(node.right,e);
        }
        return node;

    }

    //***************************************************************
    //3.  

    /**
     * 3.1          
     * @param e
     * @return
     */
    public boolean contains(E e){
        return contains(root,e);
    }

    private boolean contains(Node node,E e){
        if(node==null)
            return false;


        if(e.compareTo(node.e)==0){
            return true;
        }else if(e.compareTo(node.e)<0){
            return contains(node.left,e);
        }else{
            return contains(node.right,e);
        }
    }


    /**
     * 3.2           
     */
    public void preOrder(){
        preOrder(root);
    }
    //      node        ,     
    private void preOrder(Node node){
        if(node==null){
            return;
        }

        System.out.println(node.e);
        preOrder(node.left);
        preOrder(node.right);
    }


    /**
     * 3.3        
     */
    public void preOrderNR(){
        if (root==null){
            return;
        }

        Stack stack=new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            Node cur=stack.pop();
            System.out.println(cur.e);

            if(cur.right!=null){
                stack.push(cur.right);
            }
            if(cur.left!=null){
                stack.push(cur.left);
            }
        }
    }

    /**
     * 3.4           
     */
    public void levelOrder(){
        Queue q=new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()){
            Node cur=q.remove();
            System.out.println(cur.e);

            if(cur.left!=null){
                q.add(cur.left);
            }
            if(cur.right!=null){
                q.add(cur.right);
            }
        }
    }


    /**
     * 3.5           
     */
    public void inOrder(){
        inOrder(root);
    }
    //      node        ,     
    private void inOrder(Node node){
        if(node==null)
            return;

        inOrder(node.left);
        System.out.println(node.e);
        inOrder(node.right);
    }

    /**
     * 3.6     
     */
    public void postOrder(){
        postOrder(root);
    }


    private void postOrder(Node node){
        if(node==null)
            return;

        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.e);
    }
    //*****************************************************
    //    :
    @Override
    public String toString(){
        StringBuilder res=new StringBuilder();
        generateBSTString(root,0,res);
        return res.toString();
    }

    private void generateBSTString(Node node,int depth,StringBuilder res){

        if(node==null){
            res.append(generateDepthString(depth)+"null
");
            return;
        }

        res.append(generateDepthString(depth)+node.e+"
");

        generateBSTString(node.left,depth+1,res);
        generateBSTString(node.right,depth+1,res);
    }

    private String generateDepthString(int depth){
        StringBuilder res=new StringBuilder();
        for (int i=0;i0){
            node.right=remove(node.right,e);
            return node;
        }else { // e.compareTo(node.e) == 0
            //          
            if(node.left==null){
                Node rightNode=node.right;
                node.right=null;
                size--;
                return rightNode;
            }

            //              
            if(node.right==null){
                Node leftNode=node.left;
                node.left=null;
                size--;
                return leftNode;
            }

            //                 
            //               ,               
            //                
            Node successor=minimum(node.right);
            successor.right=removeMin(node.right);
            successor.left=node.left;
            node.left=null;
            node.right=null;
            return successor;

        }


    }

    //*****************************************************


    //*****************************************************

    public static void main(String[] args) {
//        BSTimprove bst=new BSTimprove<>();
//        int[] nums={5,4,23,4,23,534,3,34,32,189};
//        for (int num:nums){
//            bst.add(num);
//        }
//        bst.preOrder();
//        System.out.println();
//
//        //    
////        System.out.println(bst);
//
//        bst.inOrder();
//        System.out.println();
//
//        bst.postOrder();
//        System.out.println();
//
//        bst.levelOrder();

        //test2
        BSTimprove bst=new BSTimprove<>();
        Random random=new Random();

        int n=1000;
        for (int i =0;i nums=new ArrayList<>();
        while (!bst.isEmpty()){
            nums.add(bst.removeMin());
        }
        System.out.println(nums);
    }
}