二叉查找树（BST)

妖狐艹你老母 2022-04-25 02:22 152阅读 0赞

# 二叉查找树(BST) #

特殊的二叉树，又称为排序二叉树、二叉搜索树、二叉排序树。

二叉查找树实际上是数据域有序的二叉树，即对树上的每个结点，都满足其左子树上所有结点的数据域均小于或等于根结点的数据域，右子树上所有结点的数据域均大于根结点的数据域。如下图所示：

![1128337-20180805125851913-1469584927.png][]

二叉查找树通常包含查找、插入、建树和删除操作。

# 二叉查找树的查找、插入和删除 #

查找、插入和删除的代码就不一一赘述了，本文主要是记录尝试写出基本的二叉查找树的代码而已。

class BinaryNode<T> {
        public T element;
        public BinaryNode<T> left;
        public BinaryNode<T> right;
    
        public BinaryNode(T element, BinaryNode<T> left, BinaryNode<T> right) {
            this.element = element;
            this.left = left;
            this.right = right;
        }
    }
    
    public class BinarySearchTree<T> {
        private BinaryNode<T> root;
        private final Comparator<T> comparator;
    
        public BinarySearchTree(BinaryNode<T> root, Comparator<T> comparator) {
            this.root = root;
            this.comparator = comparator;
        }
    
        public void clear() {//其他节点相互引用？需要对每个节点设置为null
            root = null;
        }
    
        public boolean isEmpty() {
            return root == null;
        }
    
        public boolean containsKey(T x) {
            return containsKey(x, root);
        }
    
        private boolean containsKey(T x, BinaryNode<T> root) {
            if(root == null)
                return false;
            int result = comparator.compare(x, root.element);
            if(result < 0)
                return containsKey(x, root.left);
            else if(result > 0)
                return containsKey(x, root.right);
            return true;
        }
    
        public T findMin() {
            BinaryNode<T> minNode = findMin(root);
            return minNode == null ? null : minNode.element;
        }
    
        private BinaryNode<T> findMin(BinaryNode<T> root) {
            if(root == null)
                return null;
            if(root.left == null)
                return root;
            return findMin(root.left);
        }
    
        public T findMax() {
            BinaryNode<T> maxNode = findMax(root);
            return maxNode == null ? null : maxNode.element;
        }
    
        private BinaryNode<T> findMax(BinaryNode<T> root) {
            if(root == null)
                return null;
            if(root.right == null)
                return root;
            return findMin(root.right);
        }
    
        public void insert(T x) {
            root = insert(x, root);
        }
    
        private BinaryNode<T> insert(T x, BinaryNode<T> root) {
            if(root == null)
                return new BinaryNode<>(x, null, null);
            int result = comparator.compare(x, root.element);
            if(result < 0)
                root.left = insert(x, root.left);
            else if(result > 0)
                root.right = insert(x, root.right);
            return root;
        }
    
        public void remove(T x) {
            root = remove(x, root);
        }
    
        private BinaryNode<T> remove(T x, BinaryNode<T> root) {
            if(root == null)
                return root;
            int result = comparator.compare(x, root.element);
            if(result < 0)
                root.left = remove(x, root.left);
            else if(result > 0)
                root.right = remove(x, root.right);
            else if(root.left != null && root.right != null) {
                root.element = findMin(root.right).element;
                root.right = remove(root.element, root.right);
            } else
                root = root.left != null ? root.left : root.right;
            return root;
        }
    }

[1128337-20180805125851913-1469584927.png]: /images/20220210/638d250a38ff4af4a7c3474d5efff0c4.png