图片.png
    什么是字典树：
    字典树，又称 Trie 树，是一种树形结构。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串）。主要思想是利用字符串的公共前缀来节约存储空间。
    在实际运用中，比如我们要储存大量的单词在一个文本中，而且还要查找某个单词是否存在，如果存在，请输出出现了多少次。考虑到有大量的单词而且还要询问出现了多少次，考虑到无法用字符串直接存储并进行遍历，所以就有了字典树这种高级数据结构。字典树的主要思想是利用字符串的公共前缀来节约存储空间。

    字典树的作用：
    单词查找、字符串排序
    图中深色的节点表示单词是存在的。如：左下角表示单词：aae

    字典树的插入与查询：（leetcode208）

    1. class Trie {
    3.     //字典树节点
    4.     class Node {
    5.         Node[] next;
    6.         boolean flag;
    7.         Node() {
    8.             next = new Node[26];
    9.             flag = false;
    10.         }
    11.     }
    13.     Node root;
    14.     public Trie() {
    15.         root = new Node();
    16.     }
    18.     //字符串插入
    19.     public void insert(String word) {
    20.         Node p = root;
    21.         for(int i = 0;i < word.length();i++) {
    22.             int ind = word.charAt(i) - 'a';
    23.             if(p.next[ind] == null) p.next[ind] = new Node();
    24.             p = p.next[ind];
    25.         }
    26.         p.flag = true;
    27.     }
    29.     //查找字符串是否存在
    30.     public boolean search(String word) {
    31.         Node p = root;
    32.         for(int i = 0;i < word.length();i++) {
    33.             int ind = word.charAt(i) - 'a';
    34.             p = p.next[ind];
    35.             if(p == null) return false;
    36.         }
    37.         return p.flag;
    38.     }
    40.     //查找输入的字符串是否是前缀
    41.     public boolean startsWith(String prefix) {
    42.         Node p = root;
    43.         for(int i = 0;i < prefix.length();i++) {
    44.             int ind = prefix.charAt(i) - 'a';
    45.             p = p.next[ind];
    46.             if(p == null) return false;
    47.         }
    48.         return true;
    49.     }
    50. }