1. 字典树

Trie树，即字典树，又称单词查找树或键树，是一种树形构造，是一种哈希树的变种。

典型利用是用于统计和排序大量的字符串（但不仅限于字符串），所以常常被搜索引擎零碎用于文本词频统计。

Trie的核心思想是空间换工夫。它能最大限度地缩小无谓的字符串比拟，利用字符串的公共前缀来升高查问工夫的开销，查问效率比哈希树高。

2. 字典树的性质

  1. 除了根节点外，每一个节点都只蕴含一个字符
  2. 每个节点的所有子节点蕴含的字符都不雷同
  3. 从根节点到某个节点，门路上的字符连接起来，为该节点对应的字符串

3. 结构字典树

public class Trie {    static class TrieNode {        // 示意以后节点的值        char value;        // 示意以后节点是否是终止节点（这里不是指叶子节点，是指是否为单词的结尾）        boolean flag;        // 示意以后节点的子节点的数组，不思考大小写共有26个字母，所以初始化大小为26        TrieNode[] nextNodes = new TrieNode[26];        public TrieNode() {        }        public TrieNode(char value) {            this.value = value;        }    }    /**     * 插入一个新单词     *     * @param root 根节点     * @param str 要插入的新单词     */    public void insert(TrieNode root, String str) {        if (root == null || str == null || str.length() == 0) {            return;        }        for (int i = 0; i < str.length(); i++) {            // index示意以后字符在字符表中的地位            int index = str.charAt(i) - 'a';            // 如果该分支不存在，则创立一个新节点            if (root.nextNodes[index] == null) {                root.nextNodes[index] = new TrieNode(str.charAt(i));            }            // 把该节点赋给root，进入树的下一层            root = root.nextNodes[index];        }        // 设置以后节点为终止节点        root.flag = true;    }}

4. 查找单词是否在字典树中存在

    /**     * 查找一个单词是否存在     *     * @param root 根节点     * @param str 要查找的单词     */    public boolean search(TrieNode root, String str) {        if (root == null || str == null || str.length() == 0) {            return false;        }        for (int i = 0; i < str.length(); i++) {            // index示意以后的字符在中的字符表中的地位            int index = str.charAt(i) - 'a';            // 如果该分支不存在，则阐明不存在该字符            if (root.nextNodes[index] == null) {                return false;            }            // 把以后节点赋给root，进入树的下一层            root = root.nextNodes[index];        }        // 如果以后节点是终止节点，则阐明存在，否则不存在        return root.flag;    }