字典树又称 Trie树 ，单词查找树，前缀树，也是一种树状结构，他主要利用字符串的公共前缀来减少查询次数，最大限度地减少字符串比较，比如要查找一个字符串是否存在，或者是否存在 xxx 开头的字符串。假设字符串只包含小写字母，那么我们可以把字典树看作是一棵每个节点最多有 26 个子节点的树。字典树中根节点是不存储数据的，除了根节点以外，每个节点代表一个字符，从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。比如有 wang， yi ，bo ， yibo 等字符串，只需要把它添加到字典树中，然后在每个字符串末尾标记为一个完整的字符串即可，如图下图所示。
比如查找 wan ，因为字母 n 在字典树中没有标记，所以 wan 不是一个完整的字符串。在字典树中每个节点只需要两个变量，一个是记录子节点的数组，一个是标记从根节点到当前节点为止，是否是一个完整的字符串。
// 节点类。
class TrieNode {
boolean isWord; // 标记是否为完整字符串。
TrieNode[] children; // 子节点数组。
public TrieNode() {
isWord = false;// 默认不是完整字符串。
// 默认每个节点最多有26个子节点，还可以使用map。
children = new TrieNode[26];
}
}
这里我们规定只查询小写字母，当然如果包含其他字母的话可以使用 Map 。
public Map<Character, TrieNode> children = new HashMap<>();
字典树的常见操作是插入和查询，查询一般查询是否是一个完整字符串，或者查询是否有某个字符串的前缀，或者查询字符串的数量，或者查询某个字符串前缀的数量，但也有删除，删除比较少见。这里我们不讲那么复杂，只讲简单的插入，字符串查询和前缀查询。对于其他的操作还需要在每个节点添加一个变量计算当前节点出现的次数即可。对于删除来说必须先判断要删除的字符串存在才能执行删除操作。
字典树的插入：
先来看一下字典树的插入，他的原理就是沿着一条路径往下插入字符，如果路径上对应的节点存在，就继续往下判断下一个字符，如果不存在就创建对应的节点，当字符串插入完之后把它标记为完整的字符串，也就是说从根节点到我们标记的那个字符连接起来就是一个完整的字符串，如下图所示。
来看下代码：
// 插入字符串。
public void insert(String word) {
TrieNode parentNode = root;// 根节点。
for (int i = 0; i < word.length(); i++) {// 遍历字符串中的字符。
int index = word.charAt(i) - 'a';
// 子节点如果不存在就创建。
if (parentNode.children[index] == null)
parentNode.children[index] = new TrieNode();
parentNode = parentNode.children[index];
}
// 插入完了，标记为是一个完整的单词。
parentNode.isWord = true;
}
字典树的查询：
这里查询有两个，一个是查找前缀是否存在，一个是查找字符串是否存在，原理比较简单，直接看下代码。
// 判断 word 是否是完整的单词。
public boolean search(String word) {
TrieNode current = find(word);// 先查找。
return current != null && current.isWord;
}
// 前缀 prefix 是否存在。
public boolean startsWith(String prefix) {
return find(prefix) != null;
}
// 查询字符串 str。
private TrieNode find(String str) {
TrieNode parentNode = root;
for (int i = 0; i < str.length(); i++) {
int index = str.charAt(i) - 'a';
// 只要有一个字符节点不存在就返回null。
parentNode = parentNode.children[index];
if (parentNode == null)
return null;
}
return parentNode;
}
未完待续。。。
| 数组，滚动数组，差分数组，树状数组 | |
| 链单向表，双向链表，循环链表，跳表，异或链表 | |
| 队列，循环队列，双端队列 | |
| 栈 | |
| 散列表 | |
| 二叉树，二叉搜索树，AVL树，红黑树，字典树，哈夫曼树，线段树，笛卡尔树 | |
| 堆 | |
| 图的介绍，图的遍历，Dijkstra算法，Bellman-Ford算法，SPFA算法，Floyd算法，Prim算法，Kruskal算法，Boruvka算法，拓扑排序 |
