Trie树

Question

后在当前节点或节点结束鉴于字典树具有节​​点作为这样：

struct TrieNode { 
    map<char, TrieNode> children; 
    bool endOfWord = false; 

    TrieNode() {} 
}; 

难道是用于endOfWord布尔更好在字的结尾是真实的（情况1）

c-a-[t] <--- endOfWord = true;

或创建一个空的炭节点和具有endOfWord那里（情况2）

c-a-t-[ ] <--- endOfWord = true;

从我看到的所有教程中，他们推荐后者的选择，但这不会让事情变得更混乱吗？对于包含招手，并召唤一个线索，案件1会是什么样子

b-e-c-k-o-[n]-e-[d]

但情况2将有

b-e-c-k-o-n-[e]-d-[ ]

还是这只是我的线索是如何实现的问题？

Answer 1

我会用字母上的第一个结尾字来标记，而不是继承者。主要原因：搜索时，不需要寻找一个空的EoW后继者 - 节省CPU时间（特别是如果空的节点需要加载到CPU缓存中，但可以通过使用单个终止节点来缓解这一点也就是说，除非有人需要向孩子反馈父母 - 如果我能想象为什么有人需要它，那么会打败我）。

Answer 2

创建其他对象来表示grapf叶子有什么意义？在任何算法实现中，您都必须检查endOfWord是否设置为true或false。引入额外的对象层不会使实现更容易，这会导致内存浪费。

Answer 3

其中一个原因可能是，如果您使用特殊字符（例如代码点0），则根本不需要单词结束标志。