1. // pass end nexts，没有节点就新建，有就通过pass+1，结尾end+1。    
    2. public static class Node1 {
    3.         public int pass; // 通过多少次
    4.         public int end; // 节点是否是结尾
    5.         public Node1[] nexts; // 当多了可以使用 HashMap<Char,Node> nexts;TreeMap<Char,Node> nexts;
    7.         // char tmp = 'b'  (tmp - 'a')
    8.         public Node1() {
    9.             pass = 0;
    10.             end = 0;
    11.             // 0    a
    12.             // 1    b
    13.             // 2    c
    14.             // ..   ..
    15.             // 25   z
    16.             // nexts[i] == null   i方向的路不存在
    17.             // nexts[i] != null   i方向的路存在
    18.             nexts = new Node1[26];
    19.         }
    20.     }
    22.     public static class Trie1 {
    23.         private Node1 root;
    25.         public Trie1() {
    26.             root = new Node1();
    27.         }
    29.         public void insert(String word) {
    30.             if (word == null) {
    31.                 return;
    32.             }
    33.             char[] str = word.toCharArray();
    34.             Node1 node = root;
    35.             node.pass++;
    36.             int path = 0;
    37.             for (int i = 0; i < str.length; i++) { // 从左往右遍历字符
    38.                 path = str[i] - 'a'; // 由字符，对应成走向哪条路
    39.                 if (node.nexts[path] == null) {
    40.                     node.nexts[path] = new Node1();
    41.                 }
    42.                 node = node.nexts[path];
    43.                 node.pass++;
    44.             }
    45.             node.end++;
    46.         }
    48.         public void delete(String word) {
    49.             if (search(word) != 0) {
    50.                 char[] chs = word.toCharArray();
    51.                 Node1 node = root;
    52.                 node.pass--;
    53.                 int path = 0;
    54.                 for (int i = 0; i < chs.length; i++) {
    55.                     path = chs[i] - 'a';
    56.                     if (--node.nexts[path].pass == 0) {
    57.                         node.nexts[path] = null;
    58.                         return;
    59.                     }
    60.                     node = node.nexts[path];
    61.                 }
    62.                 node.end--;
    63.             }
    64.         }
    66.         // word这个单词之前加入过几次
    67.         public int search(String word) {
    68.             if (word == null) {
    69.                 return 0;
    70.             }
    71.             char[] chs = word.toCharArray();
    72.             Node1 node = root;
    73.             int index = 0;
    74.             for (int i = 0; i < chs.length; i++) {
    75.                 index = chs[i] - 'a';
    76.                 if (node.nexts[index] == null) {
    77.                     return 0;
    78.                 }
    79.                 node = node.nexts[index];
    80.             }
    81.             return node.end;
    82.         }
    84.         // 所有加入的字符串中，有几个是以pre这个字符串作为前缀的
    85.         public int prefixNumber(String pre) {
    86.             if (pre == null) {
    87.                 return 0;
    88.             }
    89.             char[] chs = pre.toCharArray();
    90.             Node1 node = root;
    91.             int index = 0;
    92.             for (int i = 0; i < chs.length; i++) {
    93.                 index = chs[i] - 'a';
    94.                 if (node.nexts[index] == null) {
    95.                     return 0;
    96.                 }
    97.                 node = node.nexts[index];
    98.             }
    99.             return node.pass;
    100.         }
    101.     }