什么是前缀树（Trie）

前缀树，又称 字典树，是N叉树的特殊形式。

通常来说，一个前缀树是用来 存储字符串的。前缀树的每一个节点代表一个字符串（前缀）。每一个节点会有多个子节点，通往不同子节点的路径上有着不同的字符。子节点代表的字符串是由节点本身的原始字符串，以及通往该子节点路径上所有的字符组成的。

例：

在上图示例中，我们在节点中标记的值是该节点对应表示的字符串。例如，我们从根节点开始，选择第二条路径 ‘b’，然后选择它的第一个子节点 ‘a’，接下来继续选择子节点 ‘d’，我们最终会到达叶节点 “bad”。节点的值是由从根节点开始，与其经过的路径中的字符按顺序形成的。

值得注意的是，根节点表示空字符串。

前缀树有着广泛的应用，例如 自动补全，拼写检查 等等。

如何表示一个前缀树

前缀树的特别之处在于 字符和子节点之间的对应关系。有许多不同的表示前缀树节点的方法，这里我们只介绍其中的两种方法。

第一种方法是用数组存储子节点。

例如，如果我们只存储含有字母 a 到 z 的字符串，我们可以 在每个节点中声明一个大小为26的数组来存储其子节点。对于特定字符 c，我们可以使用 c - 'a' 作为索引来查找数组中相应的子节点。

使用 Hashmap 来存储子节点。

Hashmap 的键是字符，值是相对应的子节点。

相比于数组来说 节省了空间。也更加灵活，不受长度的限制。

前缀树广泛应用于 存储字符串 和 检索关键字，特别是 和前缀相关的关键字。