从C++的数字树（trie）中找出最长的单词

对于任务，我必须制作两种方法，一种是打印出一个存储几个单词的数字树，并在实际单词旁边标记*。另一种方法应该是找到这个数字树中最长的单词。下面是定义的类（我已完成的打印方法）：从C++的数字树（trie）中找出最长的单词

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 
}

我得到了印刷法迭代和递归的混合工作，并认为找到最长的单词是相似的，这意味着所有我会的需要做的是迭代我的树，调用一个函数来检查它是否是一个单词，如果是，将它与当前最长的单词进行比较，但是当它找到最长的单词时，它不会自动返回，并且继续前进到下一个单词。我应该如何着手解决这个问题，（或者甚至是关于如何解决这个问题的一般想法，我会赞赏，因为这个课程），以我目前的实施？

来源

2015-02-10 Alex

您是否使用过调试器并单步执行代码，使用小数据样本？ – 2015-02-10 23:38:36

它怎么能知道它刚刚找到的单词是树中最长的一个词，而没有继续检查其余的单词？ – Beta 2015-02-11 00:34:00

“ics :: ArrayMap children'的关键是什么？ 'is_word'是什么意思？即什么是不是一个单词的节点？只有没有孩子的叶子有词吗？ – tofi9 2015-02-11 03:35:40

有实现这一几种方法，这里是最简单的（但效率最低的一个）：

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。这样你就可以避免重复在打印树的现有函数和这个之间执行递归的代码。

来源

2015-02-11 00:33:27

从C++的数字树（trie）中找出最长的单词

回答

相关问题