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

Question

对于一个作业，我必须做两种方法，一种是打印一棵数字树，存储几个单词，并在实际单词旁边标记一个*。另一种方法是在这棵数字树中找到最长的单词。下面是定义的类(使用我已完成的print方法)：

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

当有两个或两个以上的单词具有相同的最长长度时，该由你来定义发生了什么。

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