什么指示字符串是否存在于 trie 中

Question

如果word/string的结束点，每个视频或书中的解释都不清楚或不一致，是否有返回的特殊键或返回布尔值true。 例如我们知道trie中有"paper"这个词，现在我要找"pap"这个词，什么表示这不是一个词，怎么才能在我的trie中找到这个词呢

编辑：如果我在分支的末尾，属于最后一个节点的数组是否在每个索引上都有 nullptr？

Answer 1

两者都可以。如果 trie 仅用于测试成员资格，那么节点只需要一个布尔值来指示它是否是终端节点。如果 trie 用于将值与键相关联，则终端节点将包含这些值（或指向它们的指针）。如果有一个可区分的 nil/null 值，那么就不需要单独的布尔值——一个节点是一个终端，前提是它包含一个非零值。但是存储布尔值也是完全可以接受的。 None 这对数据结构的性质有任何真正的影响。