删除二叉搜索树中的最小值

Question

我了解算法，但不确定如何将其放入实际代码中。请帮忙！也请详细解释。除了抄录答案之外，我真的很想了解这一点。 ;)

这是我的代码：

 public boolean getLeftChild(){
    Node insertNode = root;
    while(insertNode!=null){
        insertNode = insertNode.left;
    }
    return true;
}
public Boolean removeMin(){
    Node insertNode = root;
    Node parentNode =root;
        if (insertNode.left ==null){
            insertNode.right = parentNode;
            insertNode = null;
        }else if (getLeftChild() ==true && insertNode.right != null){
            insertNode.left = null;
        }else{
            parentNode.left = insertNode.right;
    }
        return true;
}

Answer 1

首先要做的是：对于树，我强烈建议递归。

仅举一个例子：

getSmallestNode(Node node){
     if(node.left != null){
         return getSmallestNode(node.left)
     }
     return node;
}

对于删除，如果要删除二叉树中最小的（因此是"最左叶"的子级），则可能有两种情况。

情况 1：叶没有子节点，在这种情况下，只需将父节点中的相应条目设置为 null （mostLeftChild.getParent().left = null ）

情况 2：叶子有一个右子节点（不能有左子节点，因为这意味着会有一个较小的节点，并且您当前选择的节点不是最小的），在这种情况下，您将当前左侧节点替换为右侧子树的最小节点mostLeftChild.getParent().left = getSmallestFromSubtree(mostLeftChild.right)

所以现在把它变成代码，它可能看起来像这样（不能保证它真的有效）

public Node deleteSmallest(Node node){
    // haven't reached leaf yet
    if(node.left != null{
        return deleteSmallest(node.left)
    }
    // case 1, no child nodes
    if(node.right == null){
        node.getParent().left = null;
    } else { // case 2, right child node
        node.getParent().left = deleteSmallest(node.right)
    }
    return node;
}

你会用deleteSmallest(root)来称呼它