java算法之自定义二叉查找树基本操作

/** 
 * @desc: 自定义二叉查找树： 插入键值对，根据key查找元素值，删除节点，取最大（小）的元素值， 
 *                           前序（中序，后序，层次）遍历，树的高度 
 * @author: 毛会懂 
 * @create: 2021-01-05 14:11:00 
 **/ 
public class MyBinaryFindTree<K extends Comparable<K>,V> { 
    //头结点 
    private Node root; 
    //元素个数 
    private Integer size; 
 
    public MyBinaryFindTree() { 
        this.root = null; 
        size = 0; 
    } 
 
    //插入元素 
    public void put(K key, V value){ 
        root = put(root,key,value); 
    } 
 
    //根据key，获取元素 
    public V get(K key){ 
        return get(root,key); 
    } 
 
    //删除元素 
    public void delete(K key){ 
         delete(root,key); 
    } 
 
    //元素的个数 
    public Integer size(){ 
        return size; 
    } 
 
    //获取最大值 
    public V getMax(){ 
        return getMax(root); 
    } 
 
    //获取最小值 
    public V getMin(){ 
        return getMin(root); 
    } 
 
    //前序遍历 
    public Queue<Node> getPreList(){ 
        Queue<Node> queue = new LinkedList<>(); 
        getPreList(root,queue); 
        return queue; 
    } 
 
    //中序遍历 
    public Queue<Node> getMidList(){ 
        Queue<Node> queue = new ArrayBlockingQueue<>(30); 
        getMidList(root,queue); 
        return queue; 
    } 
 
    //后序遍历 
    public Queue<Node> getAfterList(){ 
        Queue<Node> queue = new ArrayDeque<>(); 
        getAfterList(root,queue); 
        return queue; 
    } 
 
    //层次遍历 
    public Queue<Node> getLayerList(){ 
        Queue<Node> queue = new ArrayDeque<>(); 
        Queue<Node> temp = new ArrayDeque<>(); 
        temp.add(root); 
        while (!temp.isEmpty()){ 
            //取队头的元素 
            Node element = temp.poll(); 
            queue.add(element); 
            if(element.left != null){ 
                temp.add(element.left); 
            } 
            if(element.right != null){ 
                temp.add(element.right); 
            } 
        } 
        return queue; 
    } 
 
    //树的最大深度 
    public Integer getTop(){ 
        return getTop(root); 
    } 
 
    private Node put(Node node,K key,V value){ 
        if(node == null){ 
            node = new Node(key,value,null,null); 
            size++; 
            return node; 
        } 
        if(key.compareTo(node.key) < 0){ 
            //插入的结点小于当前结点，则继续查找左节点 
            node.left = put(node.left,key,value); 
        }else if(key.compareTo(node.key) > 0){ 
            //插入的结点大于当前结点，则继续查找右节点 
            node.right = put(node.right,key,value); 
        }else{ 
            //插入的结点等于当前结点， 则值替换 
            node.value = value; 
        } 
        return node; 
    } 
 
    private V get(Node node,K key){ 
        if(node == null){ 
            return null; 
        } 
        if(key.compareTo(node.key) < 0){ 
            //查找的key在左节点 
            return get(node.left,key); 
        }else if(key.compareTo(node.key) > 0){ 
            //查找的key在右节点 
            return get(node.right,key); 
        }else{ 
            return node.value; 
        } 
    } 
 
    private Node delete(Node node,K key){ 
        if (node == null){ 
            return null; 
        } 
        if(key.compareTo(node.key) < 0){ 
            node.left = delete(node.left,key); 
        }else if(key.compareTo(node.key) > 0){ 
            node.right = delete(node.right,key); 
        }else{ 
            //待删除的结点为当前的node结点。 
            size--; 
            //如果没有右子树，直接返回左子树 
            if(node.right == null){ 
                return node.left; 
            } 
            //如果没有左子树，直接返回右子树 
            if(node.left == null){ 
                return node.right; 
            } 
 
            //先找此结点右节点最小的结点，它的父结点指向为null。 
            Node minNode = node.right; 
            while (minNode.left != null){ 
                minNode = minNode.left; 
            } 
            //找最小结点的上一个结点 
            Node preMinNode = node; 
            if(preMinNode.right.left !=null) { 
                preMinNode = preMinNode.right; 
                while (preMinNode.left.left != null) { 
                    preMinNode = preMinNode.left; 
                } 
            } 
            preMinNode.left = null; 
 
            //最小的结点左右结点重新指向 待删结点的左右结点。 
            minNode.left = node.left; 
            minNode.right = node.right; 
 
            //待删除的父结点指向最小的结点。 
            node = minNode; 
 
        } 
        return node; 
    } 
 
    //获取最大值 
    private V getMax(Node node){ 
        if(node == null){ 
            return null; 
        } 
        while (node.right != null){ 
            node = node.right; 
        } 
        return node.value; 
    } 
 
    //获取最小值 
    private V getMin(Node node){ 
        if(node == null){ 
            return null; 
        } 
        if(node.left != null){ 
            return getMin(node.left); 
        }else{ 
            return node.value; 
        } 
    } 
 
    //前序遍历 
    private void getPreList(Node node,Queue<Node> queue){ 
        if(node == null){ 
            return; 
        } 
        queue.add(node); 
        getPreList(node.left,queue); 
        getPreList(node.right,queue); 
    } 
 
    //中序遍历 
    private void getMidList(Node node,Queue<Node> queue){ 
        if(node == null){ 
            return; 
        } 
        getMidList(node.left,queue); 
        queue.add(node); 
        getMidList(node.right,queue); 
    } 
 
    //后序遍历 
    private void getAfterList(Node node,Queue<Node> queue){ 
        if(node == null){ 
            return; 
        } 
        getAfterList(node.left,queue); 
        getAfterList(node.right,queue); 
        queue.add(node); 
    } 
 
    //树高 
    private Integer getTop(Node node){ 
        if(node == null){ 
            return 0; 
        } 
        Integer leftMax = 0; 
        Integer rightMax = 0; 
        if(node.left != null) { 
            leftMax = getTop(node.left); 
        } 
        if(node.right != null){ 
            rightMax = getTop(node.right); 
        } 
        return leftMax > rightMax ? leftMax + 1: rightMax + 1; 
    } 
 
    //遍历的时候用到，所以修饰符为public 
    public class Node{ 
        private K key; 
        private V value; 
        private Node left; 
        private Node right; 
 
        public Node(K key, V value, Node left, Node right) { 
            this.key = key; 
            this.value = value; 
            this.left = left; 
            this.right = right; 
        } 
 
        //遍历的时候用到 
        public K getKey(){ 
            return key; 
        } 
 
        //遍历的时候用到 
        public V getValue(){ 
            return value; 
        } 
    } 
}