何为前缀树？如何生成前绿树？

又称单词查找树，字典树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

来自百度百科

例子：
一个字符串类垒的数组arr1，另一个字符串类型的数组 arr2。

• arr2 中有哪些字符，是 arr1 中出现的？请打印。
• arr2 中有哪些字符，是作为 arr1 中某个字符串前缀出现的？请打印。
• arr2 中有哪些字符，是作为 arr1 中某个字符前缀出现的？请打印 arr2 中出现次数最大的前缀。

import java.util.Arrays;
public class TrieTree {
    public static class TrieNode {
        // 单词经过的数量
        public int pass;
        // 单词截止的数量
        public int end;
        // 这里是位英文准备的，如果需要中文的话要使用 Map<Char, Node> next
        public TrieNode[] nexts;
        public TrieNode() {
            pass = 0;
            end = 0;
            // 26 个字母
            nexts = new TrieNode[26];
        }
    }
    public static class Trie {
        private TrieNode root;
        public Trie() {
            this.root = new TrieNode();
        }
        public void insert(String word) {
            if (word == null || word.length() == 0) return;
            TrieNode node = root;
            node.pass++;
            for (char c : word.toCharArray()) {
                int i = c - 'a';
                if (node.nexts[i] == null) {
                    node.nexts[i] = new TrieNode();
                }
                node = node.nexts[i];
                node.pass++;
            }
            node.end++;
        }
        public void delete(String word) {
            if (word == null || word.length() == 0) return;
            if (search(word) == 0) return;
            TrieNode node = root;
            node.pass--;
            for (char c : word.toCharArray()) {
                int i = c - 'a';
                node = node.nexts[i];
                node.pass--;
                if (node.pass == 0) {
                    node.nexts = null;
                    return;
                }
            }
            node.end--;
        }
        // word 这个单词加入过几次
        public int search(String word) {
            if (word == null || word.length() == 0) return 0;
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                int i = c - 'a';
                if (node.nexts[i] == null) return 0;
                node = node.nexts[i];
            }
            return node.end;
        }
        // 所有字符串中多少是以 pre 这个字符串作为前缀的
        public int prefixNumber(String pre) {
            if (pre == null || pre.length() == 0) return 0;
            TrieNode node = root;
            for (char c : pre.toCharArray()) {
                int i = c - 'a';
                if (node.nexts[i] == null) return 0;
                node = node.nexts[i];
            }
            return node.pass;
        }
    }
    public static void main(String[] args) {
        String[] arr1 = new String[]{"abc", "bcd", "cde", "def", "ab", "ac", "bd"};
        System.out.println(Arrays.toString(arr1));
        String[] arr2 = new String[]{"a", "b", "c", "d", "e", "f", "g"};
        System.out.println(Arrays.toString(arr2));
        Trie trie = new Trie();
        for (String s : arr1) {
            trie.insert(s);
        }
        System.out.println("arr2 中有哪些字符，是 arr1 中出现的？请打印");
        for (String s : arr2) {
            if (trie.search(s) > 0) System.out.print(s + "\t");
        }
        System.out.println();
        System.out.println("arr2 中有哪些字符，是作为 arr1 中某个字符串前缀出现的？请打印。");
        for (String s : arr2) {
            if (trie.prefixNumber(s) > 0) System.out.print(s + "\t");
        }
        System.out.println();
        System.out.println("arr2 中有哪些字符，是作为 arr1 中某个字符前缀出现的？请打印 arr2 中出现次数最大的前缀。");
        String maxTimePrefix = "";
        int num = -1;
        for (String s : arr2) {
            int prefixNumber = trie.prefixNumber(s);
            if (prefixNumber > num) {
                num = prefixNumber;
                maxTimePrefix = s;
            }
        }
        System.out.println(maxTimePrefix);
    }
}

结果

[abc, bcd, cde, def, ab, ac, bd]
[a, b, c, d, e, f, g]
arr2 中有哪些字符，是 arr1 中出现的？请打印
arr2 中有哪些字符，是作为 arr1 中某个字符串前缀出现的？请打印。
a    b    c    d    
arr2 中有哪些字符，是作为 arr1 中某个字符前缀出现的？请打印 arr2 中出现次数最大的前缀。
a