?

1 何為前綴樹

?
前綴樹 又稱之為字典樹,是一種多路查找樹,多路樹形結(jié)構(gòu),是哈希樹的變種，和hash效率有一拼，是一種用于快速檢索的多叉樹結(jié)構(gòu)。

性質(zhì)：不同字符串的相同前綴只保存一份。

操作：查找，插入，刪除

例如 字符數(shù)組
[“abc”,“bck”,“abd”,“ace”]
構(gòu)建成一顆前綴樹

---

?

2 前綴樹的代碼表示及相關(guān)操作

?

?

前綴樹中的節(jié)點(diǎn)

?

coding

public static class TrieNode {public int pass;//前綴樹節(jié)點(diǎn)被經(jīng)過的次數(shù)public int end;// 多少個字符串在此點(diǎn)結(jié)尾public TrieNode[] nexts;// 下一個節(jié)點(diǎn)// 當(dāng)字符種類很多的時候 可以使用HashMap// public Map<Character,TrieNode> trieNodeMap;// key 某條圖  value 指向的下一個節(jié)點(diǎn)public TrieNode(){// trieNodeMap = new HashMap<>();//無序使用Hash表// trieNodeMap = new TreeMap<>();// 有序使用有序表this.pass = 0;this.end = 0;nexts = new TrieNode[26];}
}

?

前綴樹代碼表示及相關(guān)操作

?

public static class Trie {private TrieNode root;//頭結(jié)點(diǎn)public Trie() {this.root = new TrieNode();}/*** 將字符串word加入到前綴樹中** @param word*/public void insert(String word) {if (word == null) {return;}char[] chars = word.toCharArray();TrieNode node = root;node.pass++;int index = 0;// 從左往右遍歷字符串for (int i = 0; i < chars.length; ++i) {// 由字符計(jì)算得出 該走哪條路index = chars[i] - 'a';//如果沒有此字符的路 則新建if (node.nexts[index] == null) {node.nexts[index] = new TrieNode();}//來到下一個節(jié)點(diǎn)node = node.nexts[index];node.pass++;}node.end++;}/*** @param word* @return 字符串在前綴樹中加入過幾次*/public int search(String word) {if (word == null) {return 0;}// 臨時前綴樹節(jié)點(diǎn) 用于遍歷前綴樹TrieNode node = root;char[] chars = word.toCharArray();int index = 0;for (int i = 0; i < chars.length; ++i) {index = chars[i] - 'a';// 沒有通往當(dāng)前字符串的路 則說明沒有加入過這個字符串 直接返回 0if (node.nexts[index] == null) {return 0;}// 下一個節(jié)點(diǎn)node = node.nexts[index];}// 所有字符的路都有  則返回最后一個節(jié)點(diǎn)的 end 值return node.end;}/*** @param pre* @return 有多少個字符串是以 pre開頭的*/public int prefixNumber(String pre) {if (pre == null) {return 0;}TrieNode node = root;int index = 0;char[] chars = pre.toCharArray();for (int i = 0; i < chars.length; ++i) {index = chars[i] - 'a';if (node.nexts[index] == null) {return 0;}node = node.nexts[index];}return node.pass;}/*** 刪除前綴樹中的字符串word** @param word*/public void delete(String word) {if (search(word) != 0) { // 前綴樹中存在字符串再刪除char[] chars = word.toCharArray();TrieNode node = root;node.pass--;int index = 0;// 遍歷每一個節(jié)點(diǎn) 將節(jié)點(diǎn)的pass值減 1for (int i = 0; i < chars.length; ++i) {index = chars[i] - 'a';if (--node.nexts[index].pass == 0) {node.nexts[index] = null;return;}node = node.nexts[index];}node.end--;}}
}