前缀树(java实现）

package class_07; /** * * 前缀树 * * 例子： * 一个字符串类型的数组arr1，另一个字符串类型的数组arr2。 * arr2中有哪些字符，是arr1中出现的？请打印 * arr2中有哪些字符，是作为arr1中某个字符串前缀出现的？请打印 * arr2中有哪些字符，是作为arr1中某个字符串前缀出现的？请打印arr2中出现次数最大的前缀。 * */ public class Code_01_TrieTree { public static class TrieNode { public int path; public int end; public TrieNode[] nexts; public TrieNode() { path = 0; end = 0; nexts = new TrieNode[26];//小写字母26个 } } public static class Trie { private TrieNode root; public Trie() { root = new TrieNode(); } public void insert(String word) { if (word == null) { return; } char[] chs = word.toCharArray(); TrieNode node = root; int index = 0; for (int i = 0; i < chs.length; i++) { index = chs[i] - 'a'; if (node.nexts[index] == null) { node.nexts[index] = new TrieNode(); } node = node.nexts[index]; node.path++; } node.end++; } public void delete(String word) { if (search(word) != 0) { char[] chs = word.toCharArray(); TrieNode node = root; int index = 0; for (int i = 0; i < chs.length; i++) { index = chs[i] - 'a'; if (--node.nexts[index].path == 0) { node.nexts[index] = null; return; } node = node.nexts[index]; } node.end--; } } public int search(String word) { if (word == null) { return 0; } char[] chs = word.toCharArray(); TrieNode node = root; int index = 0; for (int i = 0; i < chs.length; i++) { index = chs[i] - 'a'; if (node.nexts[index] == null) { return 0; } node = node.nexts[index]; } return node.end; } public int prefixNumber(String pre) { if (pre == null) { return 0; } char[] chs = pre.toCharArray(); TrieNode node = root; int index = 0; for (int i = 0; i < chs.length; i++) { index = chs[i] - 'a'; if (node.nexts[index] == null) { return 0; } node = node.nexts[index]; } return node.path; } } public static void main(String[] args) { Trie trie = new Trie(); System.out.println(trie.search("zuo")); trie.insert("zuo"); System.out.println(trie.search("zuo")); trie.delete("zuo"); System.out.println(trie.search("zuo")); trie.insert("zuo"); trie.insert("zuo"); trie.delete("zuo"); System.out.println(trie.search("zuo")); trie.delete("zuo"); System.out.println(trie.search("zuo")); trie.insert("zuoa"); trie.insert("zuoac"); trie.insert("zuoab"); trie.insert("zuoad"); trie.delete("zuoa"); System.out.println(trie.search("zuoa")); System.out.println(trie.prefixNumber("zuo")); } }