java - 删除二叉树中的值

Question

我有一个稍微工作的二叉搜索树删除值函数。唯一不起作用的情况是您尝试删除具有两个子项的根。

public boolean delete(BinaryTreeNode node, int i){
    if (node == null){
    return false;
    } else {
        if (node.getKey() == i){
            BinaryTreeNode parent = new BinaryTreeNode(0, null, null);
            parent.setLeftChild(root);
            boolean result = deleteHelper(i, node, parent);
            root = parent.getLeftChild();
            return result;
        } else {
            return deleteHelper(i, node, null);
        }
    }
}

public boolean deleteHelper(int value, BinaryTreeNode curr, BinaryTreeNode parent){
    if (value < curr.getKey()){
        if (curr.getLeftChild() != null){
            return deleteHelper(value, curr.getLeftChild(), curr);
        } else {
            return false;
        }
    } else if (value > curr.getKey()){
        if (curr.getRightChild() != null){
            return deleteHelper(value, curr.getRightChild(), curr);
        } else {
            return false;
        }
    } else {
        if (curr.getRightChild() != null && curr.getLeftChild() != null){
            curr.setKey(findMin(curr.getRightChild()).getKey());
            deleteHelper(curr.getKey(), curr.getRightChild(), curr);
        } else if (parent.getLeftChild() == curr){
            parent.setLeftChild((curr.getLeftChild() != null)?curr.getLeftChild():curr.getRightChild());
        } else if (parent.getRightChild() == curr){
            parent.setRightChild((curr.getLeftChild() != null)?curr.getLeftChild():curr.getRightChild());
        }
        return true;
    }
}

Answer 1

根据维基百科

删除有两个子节点的节点:调用要删除的节点N。不要删除N。而是选择其有序后继节点或其有序前驱节点R。将R的值复制到N，然后递归地对R调用delete，直到达到前两种情况之一。 http://en.wikipedia.org/wiki/Binary_search_tree#Deletion

您可以按如下方式尝试后继节点:

1. 获取要删除的节点的后继节点(当前)
2. 将当前的父级连接到后继者
3. 将后继者连接到当前的左子级

有关更多详细信息，请查看此链接

Java, Binary tree remove method