首先，什麽是字典樹(Trie樹)？顧名思義，就是像字典壹樣按照壹定的排序順序標準和步驟來訪問樹的節點。舉個簡單的例子，如果妳在英語詞典裏查“他”這個詞，首先要按照a-z的順序找到H的第壹個字母，然後按照同樣的順序找到E。博主要介紹的字典樹是壹種類似字典的結構。
上面提到的查找單詞的過程就是不斷尋找與被搜索單詞前綴相同的字符串，直到找到被搜索單詞的最後壹個字母。所以字典樹也叫前綴樹。
以hell、hi、new、nop為例構建字典樹，構造如下。
根據以上內容，可以得到字典樹的結構性質。
根據以上三點構建字典樹。
字典樹的構造其實比較簡單，和壹般樹的構造區別不大。接下來，將分析和解釋插入、刪除和查詢字典樹的操作。
當沒有字典樹的時候，我們需要先建立壹個字典樹。
以插入地獄為例:
然後插入單詞hit，過程如下，檢查= >如果存在，訪問/如果不存在，建立壹個新的節點，再次訪問= >直到要插入的單詞到達最後壹個字符。
字典樹的插入操作相對簡單，不需要考慮太多排序問題。
如上所述，按照壹定的標準查詢目標字符串，每個節點存儲壹個字符，從根節點到子節點的路徑形成的字符串就是對應的字符串，所以在查詢目標字符串時，從根節點開始壹步步訪問對應字符所在的節點，實際上就是匹配字符串前綴的過程。
如下圖，在字典樹中，查詢“hell”，
[圖像上傳失敗...(圖片-f028c 4-1611057619223)]
如果在字典中查不到
刪除操作比插入和查詢稍微復雜壹點，但也很簡單。刪除的前提是該詞已經存在於詞典樹中。
刪除字典樹節點需要考慮目標字符串的最後壹個字符是否是樹中的葉節點。
因為壹個單詞可能是另壹個單詞的前綴部分，如果不是葉子節點，我們只需要清空這個單詞的單詞標誌位，而不需要刪除整個“分支”。
例如，妳想刪除單詞“不”
比如妳要刪除“hell”這個詞，除了節點刪除操作是從最後壹個節點開始，而‘L’節點是葉節點之外，和第壹個刪除是壹樣的。
比如妳要刪除“hi”，其實和前兩個壹樣。可以訪問葉節點‘I’，刪除葉節點，向上訪問‘h’。由於刪除“I”後“h”仍然不是葉節點，因此您將不會繼續刪除該節點。
比如要刪除“nop”，和前面的類似，先訪問葉節點‘p’刪除，然後上移發現‘o’是葉節點，但是‘o’有單詞標簽，這裏就不繼續刪除了。
上面有幾個刪除操作，我們得到刪除的標準:
知道了這麽多字典樹的操作，相信妳對字典樹的用法也有了大致的了解。字典樹最大的功能是匹配= =字符串，前綴匹配(模糊搜索)，字符串搜索(字典)等等。
博主只鍵入了四個關鍵詞“涓涓清泉”，他們的搜索列表返回了以涓涓清泉為首的多個選項。
顧名思義，就是壹本簡單的字典，例子很少。
字典樹的構造利用空間換時間的思想和字符串的公共前綴減少了無效的字符串比較操作，從而提高了插入和查找字符串的效率。插入或查找字符串的時間復雜度為O(n)，n為字符串的長度。
當然，字典樹也有它的缺點。當插入的單詞沒有很多公共前綴時，字典樹的構造變得非常復雜和低效。
字典樹不是很難，但它是壹種非常有用的數據結構。掌握了之後，對於解決壹些關於字符串匹配和公共前綴的問題很有幫助。
當然，我們也說過字典樹有自己的缺點。因為空間是用時間換來的，如果用壹堆公共前綴很少的詞來構造字典樹，空間需求會非常大。