二分搜索树删除元素

我不是女神ヾ 2021-09-23 22:08 272阅读 0赞

# 要删除元素中的某个元素 首先要找到这个元素。 #

## 1、找到二分搜索树中的最小元素和最大元素。 ##

//寻找二搜索树的最小元素
        public E minmum() { 
            if (size == 0) { 
                throw new IllegalArgumentException("BST is empty");
            }
            return minmum(root).e;
        }
    
        private Node minmum(Node node) { 
            if (node.left == null) { 
                return node;
            }
            return minmum(node.left);
        }
    
    
        //寻找二搜索树的最大元素
        public E maxmum() { 
            if (size == 0) { 
                throw new IllegalArgumentException("BST is empty");
            }
            return maxmum(root).e;
        }
    
        private Node maxmum(Node node) { 
            if (node.right == null) { 
                return node;
            }
            return maxmum(node.right);
        }

## 2、删除找到的二分搜索树中的最小元素和最大元素。 ##

//从二分搜索树中删除最小值所在的节点，返回最小值。
        public E removeMin() { 
            E ret = minmum();
            root = removeMin(root);
            return ret;
        }
    
        //删除掉以node为根的二分搜索树中的最小节点
        //返回删除节点后新的二分搜索树的根
        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 = maxmum();
            root = removeMax(root);
            return ret;
        }
    
        //删除掉以node为根的二分搜索树中的最大节点
        //返回删除节点后新的二分搜索树的根
        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;
        }

## 3、删除二分搜索树任意元素 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70]: /images/20210923/af52383ed39447bcb086b295148d9368.png