从 C++ 中的数字树 (trie) 中查找最长的单词

Question

对于一个作业，我不得不做两种方法，一种是打印出存储几个单词的数字树，然后在实际单词旁边标记一个*。另一种方法应该是在这个数字树中找到最长的单词。这是定义的class（用我完成的打印方法）：

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
}

我得到了混合迭代和递归的打印方法，并认为找到最长的单词会类似，这意味着我需要做的就是遍历我的树，调用一个函数检查它是否是一个单词，如果是，则将其与当前最长的单词进行比较，但是当它找到最长的单词时，它不会自动return，并继续转到下一个单词。我应该如何着手解决这个问题，（或者甚至是关于如何解决这个问题的一般想法，考虑到 class），用我当前的实现？

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 returns 时，非 NULL best_match 将指向具有最长单词的节点。

由您来定义当两个或多个单词具有相同的最长长度时会发生什么。

另一条评论。考虑将遍历树的代码放入模板函数中，由 lambda class 参数化，模板 class 遍历整个树，并为每个代表一个节点的节点调用 lambda单词。这样您就可以避免重复执行打印树的现有函数和这个函数之间的递归代码。

从 C++ 中的数字树 (trie) 中查找最长的单词

Finding the longest word from a digital tree (trie) in C++

c++

tree

search

trie