数据结构与算法学习-二叉查找树

之前整理了两篇关于二叉树的文章：

征战二叉树-第一站

征战二叉树-第二站

这两篇都是基于二叉树，以及一些练习题，本篇主要对二叉查找树做一个实现，即增删改查，实际上二叉查找树也很容易理解，满足的条件就是左子节点的值小于根节点，右子节点的值大于根节点。

代码实现

public class BinarySearchTree<T extends Comparable<? super T>> {

    private Node<T> root;

    private static class Node<T> {

        public T data;
        public Node<T> left;
        public Node<T> right;

        public Node() {
        }

        public Node(T data) {
            this.data = data;
        }
    }

    public boolean isEmpty() {
        return root == null;
    }

    public boolean contains(T value) {
        return contains(value, root);
    }

    private boolean contains(T value, Node<T> root) {
        if (root == null) {
            return false;
        }
        int result = root.data.compareTo(value);
        if (result == 0) {
            return true;
        } else if (result < 0) {
            return contains(value, root.right);
        } else {
            return contains(value, root.left);
        }
    }

    public void insert(T value) {
        root = insert(root, value);
    }

    private Node<T> insert(Node<T> root, T value) {
        if (root == null) {
            return new Node<>(value);
        }
        Node<T> node = new Node<>();
        node.data = value;
        int result = root.data.compareTo(value);
        if (result > 0) {
            root.left = insert(root.left, value);
            return root;
        } else if (result < 0) {
            root.right = insert(root.right, value);
            return root;
        } else {
            return root;
        }

    }

    public boolean remove(T value) {
        return remove(root, value) != null;
    }

    private Node<T> remove(Node<T> root, T value) {

        if (root == null) {
            return null;
        }
        int result = root.data.compareTo(value);
        if (result == 0) {
            if (root.left != null && root.right != null) {
                Node<T> node = findMin(root.right);
                root.data = node.data;
                root.right = remove(root.right, node.data);
            }
            root = root.left == null ? root.right : root.left;
        } else if (result > 0) {
            root.left = remove(root.left, value);
        } else {
            root.right = remove(root.right, value);
        }
        return root;
    }

    public T findMax() {
        Node<T> max = findMax(root);
        if (max == null) {
            return null;
        }
        return max.data;
    }

    private Node<T> findMax(Node<T> root) {
        if (root == null) {
            return null;
        }
        if (root.right != null) {
            return findMax(root.right);
        }
        return root;
    }

    public T findMin() {
        Node<T> minNode = findMin(root);
        if (minNode == null) {
            return null;
        }
        return minNode.data;
    }

    private Node<T> findMin(Node<T> root) {
        if (root == null) {
            return null;
        }
        if (root.left != null) {
            return findMin(root.left);
        }
        return root;
    }

}

主要的操作就是添加和删除：

（1）添加时，就是遍历树，比根节点大，转到到右边，比根节点小，转到左边，这样遍历到最后就找到了添加的位置

（2）删除时需要先找到需要删除的节点，即和要删除的值相同的节点，找到之后，分为两种情况，一种是只有左子节点或者只有又子节点或者没有子节点，删除节点后，如果有子节点，子节点代替根节点，没有子节点，根节点就为空；第二种是需要删除的节点有左子节点和右子节点，这时候需要找到右边树的中最小的节点，将这个节点的值赋给待删除的根节点，然后就变成删除右边树的中最小的节点，变成了第一种情况，按照第一种情况处理即可。

代码地址

二叉查找树