0

我正在尝试编写一个简单的搜索引擎，它使用trie（一个节点只包含一个字符）数据结构来查找单词。当它从用户那里得到“压缩”命令时，trie 应该变成一种 patricia trie的形式。（一个节点包含与他们的孩子共同的字符串）

我已经完成了连接字符串的部分，但问题是与其父级连接的子级仍然存在。（它们应该已被删除。）我想，通过编写一个“清除”方法，我可以处理它。

这是我的解决方案，但它不起作用：

public void toPatriciaTrie() {
    toPatriciaTrie(root);
    clearTheTrie(root); // the method call is here.
}

public void clearTheTrie(Node<String> v) {
    for (Node<String> w : v.getChildren()) {
                    // finds out if the parent contains the children
                    // if yes, deletes the children.
        if (v.getElement().indexOf(w.getElement()) != -1) {
            w = null;
        }
        else if (w != null) {
            clearTheTrie(w);
        }
    }

}

这是主要和输出：

主要的：

public static void main(String[] args) {
    Trie trie = new Trie();
    System.out.println("false " + trie.contains("stack"));
    // here the second one is the name of the file containing the word 
    // and the other one is its index in the file.
    trie.addToTrie("stack", "asd.txt", 3);
    trie.addToTrie("star", "asd.txt", 5);
    trie.addToTrie("jaws", "asdf.txt", 7);
    trie.addToTrie("java", "asdadsad.txt", 9);
    System.out.println("true " + trie.contains("stack"));
    System.out.println("true " + trie.contains("star"));
    System.out.println("true " + trie.contains("jaws"));
    System.out.println("true " + trie.contains("java"));
    trie.print();
    trie.toPatriciaTrie();
    System.out.println();
    trie.print();
}

输出：

false false
true true
true true
true true
true true
j a v a w s s t a r c k 
ja a va a ws s sta ta a r ck k

我该如何处理这个问题？任何帮助将不胜感激。非常感谢！

4

1 回答 1

0

问题是您如何尝试清除孩子。

这部分：

for (Node<String> w : v.getChildren()) {
                // finds out if the parent contains the children
                // if yes, deletes the children.
    if (v.getElement().indexOf(w.getElement()) != -1) {
        w = null;
    }
    ....
}

不删除子项，它将对子项的引用设置为 null，但它使 c 中的子项保持不变。您必须告诉 v 移除孩子。

于 2013-06-30T11:08:45.953 回答