java—从二叉搜索树中删除元素

4ngedf3f  于 2021-06-30  发布在  Java
关注(0)|答案(0)|浏览(187)

我一直在研究一个二进制搜索树,它将存储一个单词列表,并将其用作拼写检查器。我一直在研究一个从bst中删除元素的方法。我实现了一个在网上找到的代码,该代码应该删除一个项,但当我运行此代码时,它将删除我要删除的项上的一个,而不是另一个。我在下面附上了我的删除方法。我让它为我的代码的其他部分返回一个布尔值。

public boolean remove(E value){
        TreeNode parent = null;
        TreeNode node = root;
        boolean done = false;

        if (root == null){
            return false;
        }

        else {
            while (!done){
                if (node == null){
                    done = true;
                }
                else if (value.compareTo(node.value) < 0){
                    parent = node;
                    node = node.left;
                }
                else if (value.compareTo(node.value) > 0){
                    parent = node;
                    node = node.right;
                }
                else {
                    done = true;
                }
            }
        }

        if (node == null){
            return true;
        }
        else if(node.left == null){
            if (parent == null){
                node = node.right;
            }
            else {
                if (value.compareTo(node.value) < 0){
                    parent.left = node.right;
                }
                else {
                    parent.right = node.right;
                }
            }
        }
        else {
            TreeNode parentOfRight = node;
            TreeNode rightMost = node.left;

            while (rightMost.right != null){
                parentOfRight = rightMost;
                rightMost = rightMost.right;
            }

            node.value = rightMost.value;
            if (parentOfRight.right == rightMost){
                parentOfRight.right = rightMost.left;
            }
            else {
                parentOfRight.left = rightMost.left;
            }
        }

        return false;
    }

暂无答案!

目前还没有任何答案,快来回答吧!

相关问题