从根节点构建树，每个节点定义两个int变量，pass和end。
pass：通过该节点的次数
end：以该节点做结尾的次数
例子：构建[“abc”,"abd"]，则各节点的pass和end取值为：root（2，0），a(2,0) ，b(2,0)，c(1,1)， d(1,1).
代码示例
public class PrefixTree { public static class Node{ public int pass; public int end; public Node[] nexts; //使用HashMap替换：----->public HashMap<Integer, Node> nexts; public Node(){ pass=0; end=0; nexts=new Node[26];//26个小写英文字母,HashMap----->nexts = new HashMap<>(); } } public static class buildTree{ private Node root; public buildTree(){ root = new Node(); } //插入字符串 public void insert(String word){ if(word==null) return; char[] str = word.toCharArray(); Node node = root; node.pass++; int index = 0; for(int i = 0; i < str.length; i++){ index = str[i] - 'a'; //hashmap----->index = (int)str[i] if(node.nexts[index]==null) //如果下一字符不存在，则创建 --->if(!node.nexts[index].containsKey(index) node.nexts[index] = new Node();//---->node.nexts.put(index,new Node()); node=node.nexts[index];//来到下一节点处--->node = node.nexts.get(index); node.pass++; } node.end++; //字符串结束，以最后一个字符结尾的节点end+1 } //查询某个字符串出现过几次 public int search(String word){ if(word==null) return 0; char[] str = word.toCharArray(); Node node = root; int index = 0; for(int i = 0; i < str.length; i++){ index = str[i]-'a'; if(node.nexts[index]==null) //若下一节点不存在，表明不存在该字符串 return 0; node = node.nexts[index]; } return node.end; } //查询所加入的字符串中，有几个是以某个字符串作为前缀的 public int prefixSearch(String word){ if(word==null) return 0; Node node = root; char[] str = word.toCharArray(); int index = 0; for(int i =0; i <str.length; i++){ index = str[i]-'a'; if(node.nexts[index]==null) return 0; node= node.nexts[index]; } return node.pass; } //从前缀树中删除某个字符串 public void delete(String word){ if(word==null) return; if(search(word)!=0){ //删除之前需要先进行查询，存在的条件下才可以删除 char[] str = word.toCharArray(); Node node = root; node.pass--; int index= 0; for(int i = 0; i <str.length; i++){ index=str[i]-'a'; if(--node.nexts[index].pass==0) { //如果下一节点的pass为0，可以直接释放后面的空间 node.nexts[index] = null; return; } node = node.nexts[index]; } node.end--;//以此字符结尾的节点的end-1 } } } public static void main(String[] args) { String[] str = {"abc","abd","acd","abc","ab"}; buildTree tree = new buildTree(); for (int i = 0; i <str.length; i++) tree.insert(str[i]); System.out.println(tree.search("abc"));//2 System.out.println(tree.search("a"));//0 System.out.println(tree.prefixSearch("a"));//5 tree.delete("abc"); System.out.println(tree.search("abc"));//1 } }
