1. 字典树

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

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

Trie的核心思想是空间换时间。它能最大限度地减少无谓的字符串比较，利用字符串的公共前缀来降低查询时间的开销，查询效率比哈希树高。

2. 字典树的性质

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

3. 字典树实例

(1) 构造字典树

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;
    }
}

(2) 查找单词是否在字典树中存在

    /**
     * 查找一个单词是否存在
     *
     * @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;
    }

4. Leetcode真题

Leetcode上第208题是要实现一个前缀树，即字典树。

题意很简单粗暴，需要实现其中四个方法： 构造方法就不多说了。 insert方法和search方法可以几乎原封不动的使用上边的代码，不过需要注意的一点是，由于题目的用例会连续调用方法，每次执行方法后，其实已经改变了root的引用，后续的方法调用就会出现问题。这里可以再使用一个引用，来保存根节点即可。 要实现startWith方法，只需要对search方法稍做改动，再将重复代码抽取个方法即可。

public class Trie {
    // 保存根节点
    TrieNode root;
    // 保存当前节点
    TrieNode curr;

    /**
     * 字典树的节点
     */
    static class TrieNode {
        // 表示当前节点的值
        char value;

        // 表示当前节点是否是终止节点（这里不是指叶子节点，是指是否为单词的结尾）
        boolean flag;

        // 表示当前节点的子节点的数组，题目说明只有小写字母，所以初始化大小为26
        TrieNode[] nextNodes = new TrieNode[26];

        public TrieNode() {
        }

        public TrieNode(char value) {
            this.value = value;
        }
    }


    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        curr = root;
        if (curr == null || word == null || word.length() == 0) {
            return;
        }
        for (int i = 0; i < word.length(); i++) {
            // index表示当前字符在字符表中的位置
            int index = word.charAt(i) - 'a';
            // 如果该分支不存在，则创建一个新节点
            if (curr.nextNodes[index] == null) {
                curr.nextNodes[index] = new TrieNode(word.charAt(i));
            }
            // 把该节点赋给root，进入树的下一层
            curr = curr.nextNodes[index];
        }
        // 设置当前节点为终止节点
        curr.flag = true;
    }

    public boolean search(String word) {
        if (searchPrefix(word)) return false;
        // 如果当前节点是终止节点，则说明存在，否则不存在
        return curr.flag;
    }

    public boolean startsWith(String prefix) {
        // 不论当前节点是否是终止节点，都返回true
        return !searchPrefix(prefix);
    }

    private boolean searchPrefix(String prefix) {
        curr = root;
        if (curr == null || prefix == null || prefix.length() == 0) {
            return true;
        }
        for (int i = 0; i < prefix.length(); i++) {
            // index表示当前的字符在中的字符表中的位置
            int index = prefix.charAt(i) - 'a';
            // 如果该分支不存在，则说明不存在该字符
            if (curr.nextNodes[index] == null) {
                return true;
            }
            // 把当前节点赋给root，进入树的下一层
            curr = curr.nextNodes[index];
        }
        return false;
    }
}

TrieNode中其实并不需要保存的当前结点的值，因为它的值其实可以通过它的索引计算出来，实际上我们本来比较的就是索引，而不是它的值。 事实上，其实连声明TrieNode的必要都没有，有兴趣的可以尝试下。

参考引用

Leetcode：leetcode-cn.com/problems/im…