在Trinode类中使用Trinode数据结构意味着什么？

Question

我在许多trie问题中看到了下面的一段代码，其中类在其内部用作defaultdict数据结构。我知道这意味着儿童是三部词典中的一部。但是，我不理解基本情况（最后一个孩子）。它没有“无”或空定义。我想知道是否有人能解释一下

class TrieNode():
    def __init__(self):
        self.children = collections.defaultdict(TrieNode)
        self.isWord = False

Answer 1

这是一种递归数据结构，通常用于树。我想尝试也是有意义的

在这种情况下，如果self.children为空（即len(self.children) == 0），则数据结构将见底。那就是你到达trie的“终点”的时候了。嗯，真的，一个结束

Answer 2

Trie通常用于从一组字符串中动态搜索给定字符串。每个字符串将由存储在self.children中的有限个可能字符组成。因此，前面的每个字符都通过self.children连接到后面的字符，每个字符都是键，每个值都是三节点对象

考虑单词{“CAN”、“取消”}。为这些词语构建的trie将是： c-a-n-c-e-l。由于两个单词都有相同的前缀，因此它们具有相同的字符序列。isWord标志用于检查一个字符是否是在我们的集合中找到的一个单词的结尾，因此字符n和l的isWord标志将为true。因此，n及其前面的所有字符在我们的集合中构成一个单词

如果一个字符是单词的最后一个字符，并且没有其他单词具有相同的前缀（基本大小写），那么它将没有子级，因此self.children将是一个空字典=={}