数据结构-Trie树

Trie 树的定义：

    Trie 树，即字典树，又称前缀树，是一种多叉树结构。典型的应用是用于统计和排序大量的字符串，它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。

Trie 的定义

Trie 树的基本性质：

1、根节点不包含字符，除根节点外每一个节点都只包含一个字符。

2、从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。

3、每个节点的所有子节点包含的字符都不相同。

Trie 树的结构：

Node节点：表示Trie 树的每个节点，里面 isWord 表示该节点是否是一个单词的末尾；next 是下一个元素的映射。外层是根节点 root 信息，以及Trie 树中存储的单词数量。

Trie 树成员变量

Trie 树中添加一个新的单词：

    思路：先把 root 节点作为当前节点 cur，遍历新增单词的每个字符，判断 cur.next 的Map 映射中是否包含当前字符，如果不包含，则新增一个映射关系，然后将 cur = cur.next.get(c)，进行下一个循环。循环结束，说明走到了单词末尾，此时需要根据cur.isWord 判断是否已经存在这个单词，如果为 cur.isWord == True，说明已经存在，则不执行添加操作，否则执行添加操作。 

add(String word)

在Trie 中是否包含某个单词：

    思路：思路跟 add 类似，只是在判断cur.next.containsKey(c)中，为false时，直接返回 fasle，循环结束之后，要看单词末尾元素的isWord 是否为True，只有为True，才能说明包含这个单词，否则可能只是一个单词的前缀。 

contains

在 Trie 中查询是否存在某个单词是有prefix 为前缀的：

    思路：思路跟 contains类似，只是循环结束后，无论最后一个元素是否是单词的末尾，都被认为是前缀。

isPrefix

在 Trie 中查找某个单词是否存在，其中 '. ' 代表任意一个字符：

    思路：由于前面的操作都是规范的字符串，所以能够通过cur = cur.next.get(c) 来遍历所有元素，但是本方法有特殊字符 '.'，无法通过该字符，找到下一个结点，所以，必须采用递归的思想。match(Node node, String word, int index)，以node为根节点的Trie 中查找单词word中的下标为index的字符。递归终止条件为：index == word.length()，字符串走完了，判断最后一个结点node是否是单词末尾；然后对 字符c 与 '.' 进行单独判断，如果c ！= '.'，则node = node.next.get(c)，继续递归执行；如果 c == '.'，则需要遍历当前node下所有的节点，然后每个节点递归执行，只要有一个节点的递归结果为true，就认为已经匹配上了。

search