Поиск длинного слова из цифрового дерева (trie) в C++

Question

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

class DTN { 
    public: 
    DTN() : 
     is_word(false), word_to_here(""), children() 
    {} 
    DTN (bool iw, std::string wth) : 
     is_word(iw), word_to_here(wth), children() 
    {} 

    bool      is_word; 
    std::string    word_to_here; 
    ics::ArrayMap<char,DTN> children; 
}; 


//Add a word correctly into a Digital Tree (of strings) 
void add_a_word (DTN& dtn, std::string prefix, std::string postfix) { 
    if (postfix.size() == 0) { 
    dtn.is_word = true; 
    return; 
    } else { 
    char first = postfix[0]; 
    if (!dtn.children.has_key(first)) 
     dtn.children[first] = DTN(false,prefix+first); 
    return add_a_word(dtn.children[first],prefix+first,postfix.substr(1)); 
    } 
} 


//Print dtn, its n children indenter, their n children indented.... 
void print_DTN_tree(const DTN& dtn, std::string indent) { 
    std::cout << indent << dtn.word_to_here << (dtn.is_word? "*" : "") << std:: endl; 
    for (auto n : dtn.children) 
    print_DTN_tree(n.second, indent+" "); 
} 


bool is_a_word (const DTN& dtn, std::string remaining_letters) { 
    if (remaining_letters.empty()) 
    return dtn.is_word;   //all letters in tree; is it a word? 
    else if (dtn.children.has_key(remaining_letters[0]) == false) 
    return false;     //some letters not in truee: it isn't a word 
    else 
    return is_a_word(dtn.children[remaining_letters[0]], //check the next letter 
        remaining_letters.substr(1)); 
    } 


void add_a_word (DTN& dtn, std::string word) { 
    add_a_word(dtn,"",word); 
} 

std::string longest_word (const DTN& dtn) { 
// add this method 
} 

Я получил метод печати для работы с соединением итерации и рекурсии, и подумал, что найти самое длинное слово будет аналогично, то есть все, что я бы нужно было бы перебирать мое дерево, вызывать функцию, которая проверяет, является ли это словом, и если да, сравните ее с текущим самым длинным словом, но когда оно найдет самое длинное слово, оно автоматически не возвращается и продолжает идти к следующему слову. Как мне решить это решение (или даже общее представление о том, как решить эту проблему, было бы оценено, учитывая класс), с моей текущей реализацией?

Answer 1

Есть несколько способов реализации этого, здесь самый простой (но наименее эффективный один):

DTN *best_match=nullptr; 

find_longest(root_dtn_node, &best_match); 

if (best_match != nullptr) 
{ 
    // ... That's the longest word here 
} 

// ================================================================ 

void find_longest(DTN &node, DTN **best_match) 
{ 
     if (
      // Check if the node is a word. If so, then if *best_match 
      // is null, or if that word is shorter than the word represent 
    ) 
     { 
      *best_match= &node; 
     } 

     // Now, recurse to all child nodes 
} 

Я думаю, вы можете понять, как заполнить пятна, отмеченные с комментариями. Когда рекурсия распадается и find_longest вернется, не-NULL best_match укажет на узел с самым длинным словом.

Это зависит от вас, чтобы определить, что происходит, когда есть два или более слова с той же самой длинной длиной.

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