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

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
}

我得到了混合迭代和递归的打印方法，并认为找到最长的单词会类似，这意味着我需要做的就是遍历我的树，调用一个函数来检查是否是一个词，如果是，就和当前最长的词比较，但是找到最长的词后，它不会自动返回，一直往下一个词看。我应该如何使用我当前的实现来解决这个问题(或者甚至是关于如何解决这个问题的一般想法，给定类(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 返回时，非 NULL best_match 将指向具有最长单词的节点。

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

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