0

我正在尝试从存储字典之类的单词的二进制搜索树中删除一个节点。DictEntry 元素包含单词、定义和将显示的定义类型的数字（字符串、图像等）。找不到单词时会引发 DictionaryException。

用户必须能够通过仅在方法中输入单词来删除条目。这些是用于删除的以下方法；

public void remove(String word) throws DictionaryException {
    if (root!=null) {
        //checks if the word is equal to the entrie's word
        if (word.equals(root.getElement().word()))
            root = replacement(root);
        else {
            // parent is the node above current
            BinaryTreeNode<DictEntry> current, parent = root;
            boolean found = false;
            // if lexicographically smaller than the root's word
            if (word.compareTo(root.getElement().word()) < 0)
                current = root.getLeft();
            // if lexicographically higher than the root's word
            else
                current = root.getRight();
            while (current != null && !found) {
                if (word.equals(current.getElement().word())) {
                    found = true;
                    if (current == current.getLeft())
                        parent.setLeft(replacement(current));
                    else
                        parent.setRight(replacement(current));
                } else {
                    parent = current;

                    if (word.compareToIgnoreCase(current.getElement()
                            .word()) < 0)
                        current = current.getLeft();
                    else
                        current = current.getRight();
                }// end if else
            }// end while
            if (!found)
                throw new DictionaryException("The entry was not found");
        }
    }
}

private BinaryTreeNode<DictEntry> replacement(BinaryTreeNode<DictEntry> node) {
    BinaryTreeNode<DictEntry> found = null;
    // check if both sides are empty
    if (node.getLeft() == null && node.getRight() == null)
        found = null;
    else if (node.getLeft() != null && node.getRight() == null)
        found = node.getLeft();
    else if (node.getLeft() == null && node.getRight() != null)
        found = node.getRight();
    // if both sides have an entry
    else {
        //helper positions
        BinaryTreeNode<DictEntry> current = node.getRight();
        BinaryTreeNode<DictEntry> parent = node;

        //moving positions
        while (current.getLeft() != null) {
            parent = current;
            current = current.getLeft();
        }// end while

        if (node.getRight() == current)
            current.setLeft(node.getLeft());
        else {
            parent.setLeft(current.getRight());
            current.setRight(node.getRight());
            current.setLeft(node.getLeft());
        }
        found = current;
    }// end if else
    return found;
}

我的问题是，每当我尝试像这样测试它时，都不会删除该节点，其中字典代表 BinarySearchTree；

// Insert and remove a word
try {
    dictionary.insert("course","A series of talks or lessons",1);
    dictionary.remove("course");
    res = dictionary.findWord("course");
    if (res == "") {System.out.println("Remove test passed");}
    else {System.out.println("Remove test failed");}
}
catch(DictionaryException e) {
    System.out.println("Remove test 4 failed");
}

我已经尝试使用我的插入方法查找和使用，但我什么也没得到，所以我假设问题出在我的删除逻辑中。

4

1 回答 1

1

乍一看，替换方法是使用 == 运算符进行节点比较。这仅比较节点的内存地址。如果要根据节点的值进行比较，则需要使用 .equals() 方法。

于 2012-11-19T09:41:22.787 回答