[데이터 구조] 자바 2 분 검색 트 리 구현

package bin_tree;

/**
 * @program: bintree
 * @description:        
 * @author: fwb
 * @create: 2019-06-05 19:45
 **/
public interface BInTree<E> {
    void add(E e);
    boolean contains(E e);
    void preOrder();//    
    void inOrder();//    
    void postOrder();//    
    E getMin();//     
    E getMax();
    E removeMin();
    E removeMax();
    void remove(E e);//      
    int size();//      
//    void floor();//              
//    void ceil();//              
//    void rank();//       
//    void select();//    ，   
}

package bin_search_tree;

import bin_tree.BInTree;

/**
 * @program: bintree
 * @description:
 * @author: fwb
 * @create: 2019-06-05 19:51
 **/
public class BinSearchTree<E extends Comparable<E>> implements BInTree<E> {

    private class Node{
        E data;
        Node left;
        Node right;

        public Node(E e) {
            data = e;
        }
    }
    private Node root;
    private int size;

//    public void add(E e) {
//        if (root == null){
//            Node node = new Node(e);
//            root = node;
//            size++;
//        }
//        //        
//        add(root,e);
//    }
//    /**
////    * @Description:       node    ，      e
////    * @Param: [node, e]
////    * @return: void
////    */
////    private void add(Node node,E e){
////        //               
////        if (node.data.compareTo(e) == 0){
////            return;
////        }
////        //      ，       （     ）
////        else if(e.compareTo(node.data) < 0 && node.left == null){
////            Node newNode = new Node(e);
////            node.left = newNode;
////            size++;
////        }
////        //      ，       （     ）
////        else if (e.compareTo(node.data) > 0 && node.right == null){
////            Node newNode = new Node(e);
////            node.right = newNode;
////            size++;
////        }
////        else if (e.compareTo(node.data) < 0){
////            //        
////            add(node.left,e);
////        }else{
////            //         
////            add(node.right,e);
////        }
////    }

    //    add  
    public void add(E e) {
        root = add(root,e);
    }
    /**
    * @Description:    node     ，     e   ，           。
    *           ，        ，             
    * @Param: [node, e]
    * @return: void
    */
    private Node add(Node node,E e){
        //    
        if (node == null){
            Node newNode = new Node(e);
            size++;
            return newNode;
        }
        //     ，    e             
        if (e.compareTo(node.data) < 0){
            node.left = add(node.left,e);
        }
        if (e.compareTo(node.data) > 0){
            node.right = add(node.right,e);
        }
        return node;
    }

    @Override
    public boolean contains(E e) {
        if (root == null){
            return false;
        }
        return contains(root,e);
    }

    //  
    private boolean contains(Node node,E e){
        if (node == null){
            return false;
        }
        if (node.data.compareTo(e) == 0){
            return true;
        }
        else if (e.compareTo(node.data) < 0){
            return contains(node.left,e);
        }else {
            return contains(node.right,e);
        }
    }

    @Override
    public void preOrder() {
        preOrder(root);
    }
    /***
    * @Description:                 
    * @Param: [node]
    * @return: void
    */
    private void preOrder(Node node) {
        if (node == null)
            return;
        System.out.println(node.data);
        preOrder(node.left);
        preOrder(node.right);
    }

    @Override
    public void inOrder() {
        inOrder(root);
    }

    /***
    * @Description:  node          
    * @Param: [node]
    * @return: void
    */
    private void inOrder(Node node){
        if (node == null){
            return;
        }
        inOrder(node.left);
        System.out.println(node.data);
        inOrder(node.right);
    }


    @Override
    public void postOrder() {
        postOrder(root);
    }

    private void postOrder(Node node){
        if (node == null){
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.data);
    }

    //             ，                ，        。
    @Override
    public E getMin() {
        if (root == null)
            throw new IllegalArgumentException("BST is empty!");
        Node node  = getMinNode(root);
        return node.data;
    }
    /**
    * @Description:    node                。
    * @Param: [node]
    * @return: bin_search_tree.BinSearchTree.Node
    */
    private Node getMinNode(Node node){
       if (node.left == null){
           return node;
       }
       return getMinNode(node.left);
    }
    //                ，        。
    @Override
    public E getMax() {
        if (root == null)
            throw new IllegalArgumentException("BST is empty!");
        Node node = getMaxNode(root);
        return node.data;
    }

    private Node getMaxNode(Node node){
        if (node.right == null){
            return node;
        }
        return getMaxNode(node.right);
    }

    @Override
    public E removeMin() {
        E result = getMin();
        root = removeMInNode(root);
        return result;
    }

    /**
    * @Description:              ，            。
    * @Param: [node]
    * @return: bin_search_tree.BinSearchTree.Node
    */
    private Node removeMInNode(Node node){
        //         
        if (node.left == null){
            Node rigthNode = node.right;
            node.right = null;
            size--;
            return rigthNode;
        }
        //              
        node.left = removeMInNode(node.left);
        return node;
    }

    @Override
    public E removeMax() {
        E result = getMax();
        root = removeMaxNode(root);
        return result;
    }

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

    /*
    HIbbard Deletion
                  ，  （        ，        ）
     */
    public void remove(E e) {
        root = remove(root,e);
    }
    /**
    * @Description:   node       e   ，            
    * @Param:
    * @return:
    */
    private Node remove(Node node,E e){
        if (node == null){
            return null;
        }
        //    .data < e,           
        if (e.compareTo(node.data) < 0){
            node.left = remove(node.left,e);
        }
        //    .data > e,           
        if (e.compareTo(node.data) > 0){
            node.right = remove(node.right,e);
        }
        //  node        （  node.data == e）
        else{
            //           
            if (node.left != null && node.right == null){
                Node leftNode = node.left;
                size--;
                node.left = null;
                return leftNode;
            }
            if (node.right != null && node.left == null){
                Node rightNode = node.right;
                size--;
                node.right = null;
                return rightNode;
            }
            if (node.right != null && node.right != null){
                //            （    ，    ）
                Node successor = getMinNode(node.right);
                //               （       ）
                successor.left = node.left;
                //                        
                successor.right = removeMInNode(node.right);
                //  node
                node.left = node.right = null;
                return successor;
            }
        }
        return node;
    }

    public int size() {
        return size;
    }

    public String toString(){
        StringBuilder res = new StringBuilder();
        genrateTreeStruct(root,0,res);
        return res.toString();
    }
    //        （      ）
    private void genrateTreeStruct(Node node,int depth,StringBuilder res){
        if (node == null){
            res.append("null" + "
");
            return;
        }
        res.append(generateGang(depth) + node.data + "
");
        genrateTreeStruct(node.left,depth + 1,res);
        genrateTreeStruct(node.right,depth + 1,res);
    }
    private String generateGang(int depth){
        StringBuilder sb = new StringBuilder();
        for (int i = 0;i < depth;i++){
            sb.append("--");
        }
        return sb.toString();
    }
}

package bin_search_tree;

import bin_tree.BInTree;

import java.util.ArrayList;
import java.util.List;


/**
 * @program: bintree
 * @description:
 * @author: fwb
 * @create: 2019-06-05 20:21
 **/
public class Test {
    public static void main(String[] args) {
        BInTree<Integer> binTree = new BinSearchTree<>();
        int[] num = new int[]{28,16,13,22,30,29,42};
        for (int i = 0; i < num.length; i++) {
            binTree.add(num[i]);
        }
        binTree.preOrder();
        System.out.println("-------------------");
        binTree.inOrder();
        System.out.println("-------------------");
        binTree.postOrder();
        System.out.println("-------------------");
        System.out.println(binTree);
        System.out.println("-------------------");
        System.out.println(binTree.getMin());
        List<Integer> list = new ArrayList<>();
        while (binTree.size() != 0){
            list.add(binTree.removeMin());
        }
        System.out.println(list);
        System.out.println(binTree.size());
    }

}