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

字典樹又稱為前綴樹或Trie樹，是處理字符串常見的數據結構。假設組成所有單詞的字符僅是“a”~"z"，請實現字典樹結構，并包含以下四個主要功能：

void insert(String word)：添加word，可重復添加。
void delete(String word)：刪除word，如果word添加過多次，僅刪除一次。
boolean search(String word)：查詢word是否在字典樹中。
int prefixNumber(String pre)：返回以字符串pre為前綴的單詞數量。
思考：

字典樹的介紹。字典樹是一種樹形結構，優點是利用字符串的公共前綴來節約存儲空間。

?

基本性質：

字典樹的基本性質如下：

• 根節點沒有字符路徑。除根節點外，每一個節點都被一個字符路徑找到。
• 從根節點到某一節點，將路徑上經過的字符連接起來，為掃過的對應字符串。
• 每個節點向下所有的字符路徑上的字符都不同。

也不需要記，看了實現，很自然的性質就理解了。

每個結點內有一個指針數組，里面有二十六個指針，分別指向二十六個字母。

如果指向某個字母的指針為空，那就是以前沒有遇到過這個前綴。

?

搜索的方法為：

(1) 從根結點開始一次搜索；

(2) 取得要查找關鍵詞的第一個字母，并根據該字母選擇對應的子樹并轉到該子樹繼續進行檢索；

(3) 在相應的子樹上，取得要查找關鍵詞的第二個字母,并進一步選擇對應的子樹進行檢索。

(4) 迭代過程……

(5) 在某個結點處，關鍵詞的所有字母已被取出，則讀取附在該結點上的信息，即完成查找。

其他操作類似處理

插入也一樣，只是轉到某個子樹時，沒有子樹，那就創建一個新節點，然后對應指針指向新節點即可。

我們給出定義就更清楚了：

public static class TrieNode {public int path; //表示由多少個字符串共用這個節點public int end;//表示有多少個字符串是以這個節點結尾的public TrieNode[] map;//哈希表結構，key代表該節點的一條字符路徑，value表示字符路徑指向的節點public TrieNode() {path = 0;end = 0;map = new TrieNode[26];}
}

path和end都是有用的，接下來會說明

insert：

	    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'; //0~25if (node.map[index] == null) {node.map[index] = new TrieNode();}//創建，繼續node = node.map[index];//指向子樹node.path++;//經過加1}node.end++;//本單詞個數加1}

	        public boolean search(String word) {if (word == null) {return false;}char[] chs = word.toCharArray();TrieNode node = root;int index = 0;for (int i = 0; i < chs.length; i++) {index = chs[i] - 'a';if (node.map[index] == null) {return false;//找不到}node = node.map[index];}return node.end != 0;//end標記有沒有以這個字符為結尾的字符串}

delete：?

	        public void delete(String word) {//如果有if (search(word)) {char[] chs = word.toCharArray();TrieNode node = root;int index = 0;for (int i = 0; i < chs.length; i++) {index = chs[i] - 'a';if (node.map[index].path-- == 1) {//path減完之后為0node.map[index] = null;return;}node = node.map[index];//去子樹}node.end--;//次數減1}}

prefixNumber：

 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.map[index] == null) {return 0;//找不到}node = node.map[index];}return node.path;//返回經過的次數即可}

好處：

1.利用字符串的公共前綴來節約存儲空間。

2.最大限度地減少無謂的字符串比較，查詢效率比較高。例如：若要查找的字符長度是5，而總共有單詞的數目是26^5＝11881376，利用trie樹，利用5次比較可以從11881376個可能的關鍵字中檢索出指定的關鍵字，而利用二叉查找樹時間復雜度是O( log2n?)，所以至少要進行log211881376=23.5次比較。可以看出來利用字典樹進行查找速度是比較快的。

?

應用：

<1.字符串的快速檢索

<2.字符串排序

<3.最長公共前綴：abdh和abdi的最長公共前綴是abd，遍歷字典樹到字母d時，此時這些單詞的公共前綴是abd。

<4.自動匹配前綴顯示后綴

我們使用辭典或者是搜索引擎的時候，輸入appl，后面會自動顯示一堆前綴是appl的東東吧。

那么有可能是通過字典樹實現的，前面也說了字典樹可以找到公共前綴，我們只需要把剩余的后綴遍歷顯示出來即可。

?

相關題目：

一個字符串類型的數組arr1，另一個字符串類型的數組arr2。

arr2中有哪些字符，是arr1中出現的？請打印。

arr2中有哪些字符，是作為arr1中某個字符串前綴出現的？請打印。

arr2中有哪些字符，是作為arr1中某個字符串前綴出現的？請打印arr2中出現次數最大的前綴。