一、定義

字典樹又稱單詞查找樹，Trie樹，是一種樹形結構，是一種哈希樹的變種。典型應用是用于統計，排序和保存大量的字符串（但不僅限于字符串），所以經常被搜索引擎系統用于文本詞頻統計。它的優點是：利用字符串的公共前綴來節約存儲空間，最大限度地減少無謂的字符串比較，查詢效率比哈希表高。?

?

?

?

?

字典樹與字典很相似,當你要查一個單詞是不是在字典樹中,首先看單詞的第一個字母是不是在字典的第一層,如果不在,說明字典樹里沒有該單詞,如果在就在該字母的孩子節點里找是不是有單詞的第二個字母,沒有說明沒有該單詞,有的話用同樣的方法繼續查找.字典樹不僅可以用來儲存字母,也可以儲存數字等其它數據。

二、java代碼實現

//字典樹的java實現public class Trie {private TrieNode root;public Trie() {root = new TrieNode();root.wordEnd = false;}public void insert(String word) {TrieNode node = root;for (int i = 0; i < word.length(); i++) {Character c = new Character(word.charAt(i));if (!node.childdren.containsKey(c)) {node.childdren.put(c, new TrieNode());}node = node.childdren.get(c);}node.wordEnd = true;}public boolean search(String word) {TrieNode node = root;boolean found = true;for (int i = 0; i < word.length(); i++) {Character c = new Character(word.charAt(i));if (!node.childdren.containsKey(c)) {return false;}node = node.childdren.get(c);}return found && node.wordEnd;}public boolean startsWith(String prefix) {TrieNode node = root;boolean found = true;for (int i = 0; i < prefix.length(); i++) {Character c = new Character(prefix.charAt(i));if (!node.childdren.containsKey(c)) {return false;}node = node.childdren.get(c);}return found;}}public class TrieNode {Map<Character, TrieNode> childdren;boolean wordEnd;public TrieNode() {childdren = new HashMap<Character, TrieNode>();wordEnd = false;}}

?

轉載于:https://www.cnblogs.com/gaopeng527/p/4887765.html

總結

以上是生活随笔為你收集整理的字典树（Trie）的java实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。