從根節(jié)點構(gòu)建樹，每個節(jié)點定義兩個int變量，pass和end。
pass：通過該節(jié)點的次數(shù)
end：以該節(jié)點做結(jié)尾的次數(shù)
例子：構(gòu)建[“abc”,"abd"]，則各節(jié)點的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) //如果下一字符不存在，則創(chuàng)建 --->if(!node.nexts[index].containsKey(index) node.nexts[index] = new Node();//---->node.nexts.put(index,new Node()); node=node.nexts[index];//來到下一節(jié)點處--->node = node.nexts.get(index); node.pass++; } node.end++; //字符串結(jié)束，以最后一個字符結(jié)尾的節(jié)點end+1 } //查詢某個字符串出現(xiàn)過幾次 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) //若下一節(jié)點不存在，表明不存在該字符串 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){ //刪除之前需要先進(jìn)行查詢，存在的條件下才可以刪除 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) { //如果下一節(jié)點的pass為0，可以直接釋放后面的空間 node.nexts[index] = null; return; } node = node.nexts[index]; } node.end--;//以此字符結(jié)尾的節(jié)點的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 } }
