Как распечатать слова в дереве с вектором с определенным префиксом

Question

В настоящее время я работаю над проектом, в котором мне нужно распечатать слова в дереве, которые соответствуют заданному префиксу, заданному пользователем с использованием строкового вектора для распечатки слов.Тем не менее, у меня возникают проблемы с началом работы, и я буду рад любым предложениям, которые вы, ребята, могли бы дать мне.

Это пример того, что я имею в виду

Слова в тексте {app, address, add, beg, cow, mice} префикс данного объявления с использованием вектора для распечатки слов, содержащих префикс ad: address add

Большое спасибо за любую помощь, которую вы предоставляете.

Answer 1

Перво-наперво, дерево - это дерево.

В дереве все слова с заданным префиксом (скажем, ad) фактически сохраняются в поддереве вашего дерева, к которому осуществляется доступ при поиске префикса ad.
. Таким образом, чтобы напечатать всеСлова в вашем дереве, имеющие заданный префикс, выполняются в 2 этапа:

1. Найти узел node, соответствующий вашему префиксу
2. Список всех слов в поддереве с корнем в node.

Вот псевдокод:

find_all_words_starting_with(string prefix, trieNode node, int depth){
    if (depth == length(prefix)){
        suffix = empty_string
        print_all_words_with_prefix(prefix, suffix, node)
    } else {
        letter = prefix[depth]
        if (node.hasChild(letter)){
            find_all_words_starting_with(prefix, node.getChild(letter), depth+1)
        } else { // no word with the correct prefix
            return
        }
    }
}

print_all_words_with_prefix(prefix, suffix, node){
    if (node.isCompleteWord){
        print(prefix + suffix)
    }
    for each letter c in the alphabet {
        if (node.hasChild(c)){
            print_all_words_with_prefix(prefix, suffix + c, node.getChild(c))
        }
    }
}

find_all_words_starting_with выполняет первую часть работы.Он находит узел, соответствующий префиксу, и вызывает вторую функцию print_all_words_with_prefix, которая напечатает все полные слова в поддереве.

Answer 2

Это сильно зависит от реализации дерева, хотя я приведу пример дерева ниже.

Каждый набор содержит три вещи:

• Связка ветвей
• Корень (может быть нулевым)
• bool, который говорит, является ли илине этот три представляет полное слово

На основе этого мы можем делать такие вещи, как добавление слов в три, проверять, есть ли слово в три и применять функцию ко всем словам вTrie.Я предоставляю функции-члены для выполнения каждой из этих задач.

#include <memory>
#include <iterator>

struct WordTrie {
    static int index_from_char(char c) {
        return (unsigned char)c; 
    }
    static int char_from_index(int index) {
        return (char)(unsigned char)index; 
    }
    std::unique_ptr<WordTrie[]> branches; 
    WordTrie* root; 
    bool is_complete_word = false; 
    // Make an empty Trie
    WordTrie() : branches(nullptr), root(nullptr) {}
    // Make a WordTrie with the given root
    WordTrie(WordTrie* root) : branches(nullptr), root(root) {}


    int get_index_in_root() const {
        WordTrie const* branch_zero = root->branches.get();
        return std::distance(branch_zero, this); 
    }
    void append_char(std::string& s) {
        if(root != nullptr) {
            s += char_from_index(get_index_in_root()); 
        }
    }
    void add_word(char const* str, int length) {
        if(length > 0) {
            char c = *str; 
            if(branches == nullptr) {
                branches.reset(new WordTrie[256]); 
                for(int i = 0; i < 256; i++) {
                    branches[i].root = this; 
                }
            }
            branches[index_from_char(c)].add_word(str + 1, length - 1); 
        } else {
            is_complete_word = true; 
        }
    }
    bool has_word(char const* str, int length) {
        if(length == 0) {
            return is_complete_word; 
        }
        return branches[index_from_char(*str)].has_word(str + 1, length - 1); 
    }
    bool has_word(std::string const& s) {
        return has_word(s.data(), s.size()); 
    }
    template<class F>
    void apply_over_words_in_trie(std::string const& word, F&& func) {
        if(is_complete_word) {
            func(word); 
        }

        // Exit if there are no branches
        if(branches == nullptr) return; 
        //Add character to 'word'
        std::string new_word = word + '_';
        for(int i = 0; i < 256; i++) {
            new_word.back() = char_from_index(i); 
            branches[i].apply_over_words_in_trie(new_word, func); 
        }
    }
};