数据结构字典树

字典树 Trie

Trie发音为"try"或"tree"并源自reTrie val这一术语
又被称为字根树（prefix tree），它能够高效地进行字符串匹配。比如在查字典时
我们依次根据每个字母的位置进行查找：w -> o -> r -> d -> s.

在计算机领域中我们通常采用树形数据结构来存储词汇以便提高查找过程的效率

该图形展示了一个Trie结构中插入单词集合 {"APP","APPLE","B","BI","CA"}后的组织情况。
通过观察上图可知，在该前缀树中存在所有这些prefix：{'A','B','C','AP','APP','APPL','APPLE','BI','CA'}。
然而，在字典中"APP"和"A P PLE"被视为两个不同的单词。
这时可以采用特殊标记节点的方式标识单词结尾 - 如在示例图形中所示，在插入'APP'时，在最后一个'P'节点添加一个特殊子节点。
另一种方法是在TrieNode节点中增加一个标志位或字段来记录该节点是否是某个完整单词的结束点。

总结一些性质:

1. 根节点处于空的状态