Патриция Три

Question

Я пытаюсь написать простую поисковую систему, которая использует структуру данных 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 

Как я могу справиться с этой проблемой? Любая помощь будет оценена. Большое спасибо!

Answer 1

Проблема в том, как вы пытаетесь очистить детей.

Эта часть:

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;
    }
    ....
}

Не удаляет дочерний элемент, он устанавливает ссылку на дочерний элемент в нулевом значении, но оставляет дочерние элементы в c нетронутыми. Вы должны сказать v, чтобы удалить ребенка.