为什么这种迭代的 trie-traversal 不能在查询时产生正确的单词？

Question

所以，这是我的困境：我试图遍历 trie 数据结构以找到第 n 个单词。

对于那些不熟悉的人，trie 是一种基于压缩的数据结构，它允许您插入一系列单词，并按字典顺序对它们进行排序，但每个节点都是它自己的单独字母，因此分支和拼写成各自的词（如果不清楚，请有更具体定义的人修复！）。

树中的每个节点都有一个包含 26 个节点的数组来表示字母表中的 26 个字母。拼出一个单词后，数组 (isWord) 中该单词最后一个字符的布尔值将被标记为真。 {a, and, are, art} 等词中的词也是如此； “a”是一个词，因此，这个字母的 isWord 被设置为 true。但是，“and”中的字母被附加到“a”上，而“d”被标记为单词。

介绍完了，我的问题来了：递归做这件事对我来说非常困难，所以我尝试迭代地做。我非常非常接近解决方案，但由于某种原因，当我调用 nthWord(int n) 时，一些单词被跳过了。从本质上讲，该方法应该遍历树（按照 trie 的属性的字母顺序排列）并找到顾名思义的第 n 个单词。但是，如前所述，有时该方法会跳过 trie 中的单词，即使它保证它们被添加到 trie 中（并且 isWord 布尔值也总是正确的）。我已经解决这个问题大约 3 天了，我很迷茫。

我希望输出是序列中的第 n 个单词（来自非常大的单词 .txt 文件），但有时它会跳过某些单词。如果 j 被分配给 -1，像 "aardvark" 这样以同一个字母的 2 开头的词被计算在内，但其他的被跳过。相反，如果它被分配为 0，则其他单词将被计算在内，但以两个相同字母开头的单词将被跳过。

编辑：我还应该声明 nthWord(...) 方法不处理重复的单词。 Trie 存储每个单词在该单词的最后一个字符中出现的频率。因此，在这种情况下，重复的单词不是问题。

Answer 1

下面是本题的递归解法（比较直观）。只需将其视为树问题，您必须从左到右遍历树并尝试找到第 N 个单词。

您可以从根节点进行 DFS。保留一个变量来存储你到目前为止访问过的单词数（你访问过的带有 isWord 的节点数）。当你到达第 N 个单词时，return 个单词。

代码应该是这样的。我刚刚写了一个模板代码 -

def findWord(TrieNode,word):
    global N
    if TrieNode.isWord:
        if N == 0:
            return word
        else:
            N -= 1

    for each in TrieNode.children:
        if each is not None:
            word += each.character
            res = findWord(N,each,word)
            if len(res) > 0:
                return res
            word = word[:-1]
    return ''
N = input()
findWord(root,'')

为什么这种迭代的 trie-traversal 不能在查询时产生正确的单词？

Why does this iterative trie-traversal not produce the correct word upon a query?

java

string

algorithm

trie

data-structures