在计算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。
Trie这个术语来自于retrieval。根据词源学，trie的发明者Edward Fredkin把它读作/ˈtriː/ “tree”。但是，其他作者把它读作/ˈtraɪ/ “try”。
i)根节点不包含字符，除根节点外的每一个子节点都包含一个字符。 ii)从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。 iii)每个节点的所有子节点包含的字符互不相同。
优点：插入和查询的效率很高，都为O(m)，其中 m 是待插入/查询的字符串的长度。 缺点：空间复杂度高。
词频统计： 输入 输入的第一行为一个正整数n，表示词典的大小，其后n行，每一行一个单词（不保证是英文单词，也有可能是火星文单词哦），单词由不超过10个的小写英文字母组成，可能存在相同的单词，此时应将其视作不同的单词。接下来的一行为一个正整数m，其后m行，每一行一个字符串，该字符串由不超过10个的小写英文字母组成。 输出 对于每一个询问，输出一个整数Ans,表示词典中以给出的字符串为前缀的单词的个数。
public class p1014 { public static void main(String args[]){ Scanner sc = new Scanner(System.in); int m = Integer.parseInt(sc.nextLine()); List<String> question = new ArrayList<String>(); for(int i=0;i < m;i++){ question.add(sc.nextLine()); } int n = Integer.parseInt(sc.nextLine()); List<String> answer = new ArrayList<String>(); for(int j = 0; j < n; j++){ answer.add(sc.nextLine()); } List<Integer> res = new ArrayList<Integer>(); TrieTree tree = new TrieTree(); for(int j=0;j<question.size();j++){ tree.insert(question.get(j)); } for(int i=0;i<answer.size();i++){ String ans = answer.get(i); int r = tree.findStartWith(ans); res.add(r); } for(int i=0;i<res.size();i++){ System.out.println(res.get(i)); } } } class TrieTree{ private class TrieNode{ TrieNode[] children = new TrieNode[26]; boolean isLeaf; char val; int prefixNum; public TrieNode(char val){ this.val = val; this.isLeaf = false; this.prefixNum = 0; } } TrieNode root; public TrieTree(){ root = new TrieNode(' '); } public void insert(String word){ TrieNode cur = root; char[] data = word.toLowerCase().toCharArray(); for(int i=0;i<data.length;i++){ int index = data[i] - 'a'; if(cur.children[index]==null){ cur.children[index] = new TrieNode(data[i]); } cur = cur.children[index]; cur.prefixNum++; } cur.isLeaf = true; } public int findStartWith(String s){ TrieNode cur = root; char[] data = s.toLowerCase().toCharArray(); for(int i = 0;i<data.length;i++){ int index = data[i] - 'a'; if(cur.children[index]==null){ return 0; } cur = cur.children[index]; } return cur.prefixNum; } }