对于BST删除算法中递归的疑问

Question

老师您好！
①在BST删除元素的那个算法中，我不是很清楚老师写的那个算法中的递归终止条件是什么（没有像平时那样很清楚的写出来，也许是我太菜 -.-）
②在①的基础上我仔细思考想像之前那样明显的表现出递归终止条件，并结合BST添加算法中递归条件的简化那个想法，写出了以下程序，总体思想是根据：左右两边是空时这两种情况是Hibbard Deletion的特例。代码如下不知是否正确（测试了感觉因该没问题）

    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 ) {
            //根据空也是一棵树，我们把待删除结点的后继分成空和非空两种情况考虑
            if(node.right == null) {
                return removeMin(node);
            } else {
                Node successor = minimum(node.right);
                successor.right = removeMin(node.right);
                successor.left = node.left;
                node.left = node.right = null;
                return successor;
            }
        }
        //递归部分
        if( e.compareTo(node.e) < 0 ){
            node.left = remove(node.left,e);
            return node;
        } else {
            node.right = remove(node.right, e);
            return node;
        }
    }

Answer 1

liuyubobobo 2019-08-19 03:11:19

在课程的代码中：https://github.com/liuyubobobo/Play-with-Data-Structures/blob/master/06-Binary-Search-Tree/12-Remove-Elements-in-BST/src/BST.java

245行，246行，就是递归的终止条件，即当node为空时，返回空。

整个remove(Node node, E e)的语义是，在以node为根节点的二分搜索树中删除元素e，并且返回删除后的二分搜索树的根节点。当node为空时，肯定不包含元素e，直接返回空就好了。

======

你的代码整体思路没有问题，但是有一个小bug。在node.right == null的时候，应该删除removeMax(node)。因为此时要删除的节点是node，node->right是空，说明node是当前这棵树的最大元素，node的左子树中的所有元素，肯定比node小，所以要删除max，而不是min：）

继续加油！：）

• 提问者 程序员不会说方言 #1

  非常感谢！