前缀树：
假设一个字符串数组，“abcd”,"bcd","gef" , 构建一颗树，字母是在路径上，节点上最基本的存储的信息包括：
以这个节点结尾的 字符串的数量；
经过这个节点的字符串的数量；
一个字符串类型的数组arr1，另一个字符串类型的数组arr2；
（1）arr2中有哪些字符，是arr1中出现的？请打印
（2）arr2中有哪些字符，是作为arr1中某个字符串前缀出现的？请 打印
（3）arr2中有哪些字符，是作为arr1中某个字符串前缀出现的？请打印 arr2中出现次数最大的前缀
1 package my_basic.class_7; 2 3 public class Code_00_TrieTree { 4 //前缀树 5 public static class TrieNode{ 6 public int end; 7 public int path; 8 public TrieNode[] nexts; 9 10 public TrieNode() { 11 end = 0; 12 path = 0; 13 nexts = new TrieNode[26]; //之前没写 空指针 14 } 15 16 } 17 18 public static class Trie{ 19 private TrieNode root; 20 public Trie() { 21 root = new TrieNode(); 22 } 23 24 public void insert(String word) { 25 if (word == null) { 26 return; 27 } 28 char[] chs = word.toCharArray(); 29 int index = 0; 30 TrieNode node = root; 31 for (int i = 0; i < chs.length; i++) { 32 index = chs[i] - 'a'; 33 if (node.nexts[index] == null) { 34 node.nexts[index] = new TrieNode(); 35 36 } 37 node = node.nexts[index]; 38 node.path++; 39 } 40 node.end++; 41 } 42 43 public int search(String word) { 44 if (word == null) { 45 return 0; 46 } 47 char[] chs = word.toCharArray(); 48 int index = 0; 49 TrieNode node = root; 50 for (int i = 0; i < chs.length; i++) { 51 index = chs[i] - 'a'; 52 if (node.nexts[index] == null) { 53 return 0; 54 } 55 node = node.nexts[index]; 56 } 57 return node.end; 58 } 59 60 public void delete(String word) { 61 if (word == null) { 62 return; 63 } 64 char[] chs = word.toCharArray(); 65 int index = 0; 66 TrieNode node = root; 67 for (int i = 0; i < chs.length; i++) { 68 index = chs[i] - 'a'; 69 if (--node.nexts[index].path == 0) { 70 node.nexts[index] = null; //后面的节点直接删去 71 return; 72 } 73 node = node.nexts[index]; 74 } 75 node.end--; 76 } 77 78 public int prefixNumber(String word) { 79 if (word == null) { 80 return 0; 81 } 82 char[] chs = word.toCharArray(); 83 int index = 1; 84 TrieNode node = root; 85 for (int i = 0; i < chs.length; i++) { 86 index = chs[i] - 'a'; 87 if (node.nexts[index] == null) { 88 return 0; 89 } 90 node = node.nexts[index]; 91 } 92 return node.path; 93 } 94 } 95 96 public static void main(String[] args) { 97 String[] arr1 = {"abc","bcd","def","bcf"}; 98 String[] arr2 = {"b","a","bc"}; 99 Trie trie = new Trie(); 100 for (int i = 0; i < arr1.length; i++) { 101 trie.insert(arr1[i]); 102 } 103 //arr2中有哪些字符，是arr1中出现的 104 for (int i = 0; i < arr2.length; i++) { 105 if (trie.search(arr2[i]) != 0) { 106 System.out.print(arr2[i] + " "); 107 } 108 } 109 System.out.println(" "); 110 System.out.println("==================================="); 111 //arr2中有哪些字符，是作为arr1中某个字符串前缀出现的？ 112 for (int i = 0; i < arr2.length; i++) { 113 if (trie.prefixNumber(arr2[i]) != 0) { 114 System.out.print(arr2[i] + " "); 115 } 116 } 117 System.out.println(" "); 118 System.out.println("==================================="); 119 120 String res = null; 121 int pre = 0; 122 for (int i = 0; i < arr2.length; i++) { 123 int prefixNum = trie.prefixNumber(arr2[i]); 124 if (prefixNum != 0) { 125 System.out.print(arr2[i] + " "); 126 if(prefixNum >= pre) { 127 res = arr2[i]; 128 pre = prefixNum; 129 } 130 } 131 } 132 System.out.println(); 133 System.out.println(res); 134 135 // Trie trie = new Trie(); 136 // System.out.println(trie.search("zuo")); 137 // trie.insert("zuo"); 138 // System.out.println(trie.search("zuo")); 139 // trie.delete("zuo"); 140 // System.out.println(trie.search("zuo")); 141 // trie.insert("zuo"); 142 // trie.insert("zuo"); 143 // trie.delete("zuo"); 144 // System.out.println(trie.search("zuo")); 145 // trie.delete("zuo"); 146 // System.out.println(trie.search("zuo")); 147 // trie.insert("zuoa"); 148 // trie.insert("zuoac"); 149 // trie.insert("zuoab"); 150 // trie.insert("zuoad"); 151 // trie.delete("zuoa"); 152 // System.out.println(trie.search("zuoa")); 153 // System.out.println(trie.prefixNumber("zuo")); 154 155 156 } 157 }