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 に答える