二分搜寻树

什么是树？

树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的构造，很象自然界中的树那样。

二分搜寻树的每一个节点的值都大于左子树的所有节点的值，同时小于其右子树的所有节点的值，每一颗子树都是一颗二分搜寻树。

须要留神的是二分搜寻树并不一定每个节点都有子节点，并且存储的元素必须有可比拟值。

向二分搜寻树增加元素

如上图所示，咱们如果想插入 28 元素，咱们须要判断插入在根节点的左孩子还是右孩子，28 比 41 小，所以要插入在左孩子里，而后比拟 22，发现比 22 大所以要比拟 22 的右孩子，而后比拟 33，发现比 33 小所以就比拟 33 的左孩子，然而发现 33 没有左孩子了，这个时候咱们就能够将 28 插入在 33 的左孩子地位。

应用递归实现增加操作

public class BST<E extends Comparable<E>> {
        private class Node {
            private E e;
            // 定义左节点和右节点
            private Node left, right;
            public Node(E e) {
                this.e = e;
                left = null;
                right = null;
            }
        }
        private Node root;
        private int size;
        public int size() {return size;}
        public boolean isEmpty() {return size == 0;}
        public void add(E e) {root = add(root, e);
        }
        // 向以 node 为根的二分搜寻树中插入元素 E，递归算法
        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;
        }
}

二分搜寻树查问元素

具体实现逻辑和增加相似，都是应用递归来实现。

    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 contains(node.left, e);
        } else if (e.compareTo(node.e) > 0) {return contains(node.right, e);
        }
        return true;
    }

二分搜寻树的前序遍历

先拜访这个节点，再拜访这个节点的左子树，最初拜访这个节点的右子树，这就是前序遍历。

对于遍历操作，两颗子树都要顾及。

    // 二分搜寻树的前序遍历
    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);
    }

二分搜寻树的中序遍历

先拜访这个节点左子树，再拜访这个节点，最初拜访这个节点的右子树，这就是中序遍历。

打印输出的后果是排序好的数据。

    // 中序遍历
    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);
    }

二分搜寻树的后序遍历

先拜访这个节点左子树，再拜访这个节点的右子树，最初拜访这个节点，这就是后序遍历。

    // 后序遍历
    public void postOrder(){postOrder(root);
    }
    // 后序遍历以 node 为根的二分搜寻树，递归算法
    private void postOrder(Node node){if (node == null) {return;}
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.e);
    }

二分搜寻树的层序遍历

层序遍历其实就是广度优先遍历。

咱们能够借助队列来实现层序遍历。

在一开始的时候咱们将根节点放入队列中。而后拜访 28 来进行操作。

之后咱们将 28 的左右两个孩子别离入队，之后进行操作。

而后拜访 16 和 30，将 16 的左右孩子和 30 的左右孩子放入队列。

public void levelOrder(){Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){Node cur = queue.remove();
            System.out.println(cur.e);
            if (cur.left != null){queue.add(cur.left);
            }
            if (cur.right != null){queue.add(cur.right);
            }
        }
}

删除最大和最小元素

删除最小元素的根本逻辑为，先获取到最小元素，而后调用删除函数，从根节点登程递归查问左子树是否为 null，如果为 null 则将右子树返回到 node 的左子树上。不论右子树是否为 null 都能够返回到左子树。删除最大元素同理。

    // 寻找二分搜寻树的最小元素
    public E minimum() {if (size == 0) {return null;}
        return minimum(root).e;
    }
    private Node minimum(Node node) {if (node.left == null) {return node;}
        return minimum(node.left);
    }
    // 寻找二分搜寻树的最大元素
    public E maximum() {if (size == 0) {return null;}
        return maximum(root).e;
    }
    private Node maximum(Node node) {if (node.right == null) {return node;}
        return maximum(node.right);
    }
    // 二分搜寻树中删除最小值的元素，返回最小值
    public E removeMin() {E ret = minimum();
        root = removeMin(root);
        return ret;
    }
    private Node removeMin(Node node) {if (node.left == null) {
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }
        node.left = removeMin(node.left);
        return node;
    }
    // 二分搜寻树中删除最大值的元素，返回最大值
    public E removeMax() {E ret = maximum();
        root = removeMax(root);
        return ret;
    }
    private Node removeMax(Node node) {if (node.right == null) {
            Node leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }
        node.right = removeMax(node.right);
        return node;
    }

二分搜寻树删除任意节点

如果咱们要删除 58 节点，咱们须要从 58 的子节点中获取到比 58 大并且离 58 最近的一个节点来当新的节点。

也就是 58 的右节点中的最左根节点就是满足咱们条件的值。

咱们须要删除 S 节点，而后将 S 节点挪动到 D 节点。而后将 D 节点的左右子节点赋给 S 节点，最初删除 D 节点。

    // 从二分搜寻树中删除为 e 的节点
    public void remove(E e) {root = remove(root, e);
    }
    private Node remove(Node node, E e) {if (node == null) {return null;}
        if (e.compareTo(node.e) < 0) {node.left = remove(node.left, e);
            return node;
        } else if (e.compareTo(node.e) > 0) {node.right = remove(node.right, e);
            return node;
        }else{
            // 待删除的左子树为空的状况
            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 = node.right = null;
            return successor;
        }
    }