這次分享的Trie字典樹，是數據結構專題中的一個分支，認識了解Trie這種樹型數據結構，對構建算法與數據結構知識體系有一定的幫助。
我對Trie樹的理解：把字符串都串接起來，消滅不必要的存儲，利用的就是字符串的公共前綴。
其實對於它的理解，你理解了這句話即可👇
利用字符串的公共前綴來減少查詢時間，最大限度的減少無謂的字符串比較，查詢效率比哈希樹高。
如果你還不了解什麼是Trie數據結構的話，或者知道一些，但是對於它具體是如何實現一個簡單Trie樹時，那麼這篇文章可能適合你閱讀。
那麼圍繞以下幾個點來展開介紹Trie樹👇
聯繫👉TianTianUp，遇到問題的話，可以聯繫作者噢，願意陪你一起學習一起探討問題。
基本概念首先，我們對Trie樹得做一些基本的了解。Trie樹中文名叫字典樹，前綴樹等，接下來我就以字典樹稱呼。
我們來看下維基百科對它的描述吧⬇️
在計算機科學中，trie，又稱前綴樹或字典樹，是一種有序樹，用於保存關聯數組，其中的鍵通常是字符串。與二叉查找樹不同，鍵不是直接保存在節點中，而是由節點在樹中的位置決定。一個節點的所有子孫都有相同的前綴，也就是這個節點對應的字符串，而根節點對應空字符串。一般情況下，不是所有的節點都有對應的值，只有葉子節點和部分內部節點所對應的鍵才有相關的值。
樸實無華的描述，其實我們看一張圖就能看明白了~，我在網上找了一張不錯的圖，具體的出處，這裡就不補充了，因為實在找不到原作者~
字典樹圖解1這裡需要說明的內容就是，一般而言，應該是用一個點來表示一個字符，這裡為了更好的說明，所以我就是用邊來描述字符。
可以發現，這棵字典樹用邊來代表字母，而從根結點到樹上某一結點的路徑就代表了一個字符串。舉個例子， 1→2→6表示的就是字符串 aba 。
再比如，1→4→8構成的字符串是ca，那麼如果在往下拓展的話，我們是不是有 caa,cab，那麼他們都會經過1→4→8，這些路徑，說明他們是有一段公共的前綴，這個前綴的內容就是ca，說道這裡，我們就知道字典樹利用的就是字符串的前綴來解決問題。
那麼具體它有哪些性質的話，我們下文介紹一下~
基本性質對於上述概念有了一定的理解後，我們接下來就看下Trie樹的基本性質。
可以根據這個，大體上分成三個點來說👇
根節點不包含字符，除根節點外，每個節點只包含一個字符。從根節點到某一個節點，路徑上經過的字符連接起來，為該節點對應的字符串。接下來我們可以稍微分析一下，可以結合一個圖來看看👇
我們通過拿how,hi,her,hello,so,see這6個字符串構造出來的就是下面圖這個樣子。
圖解Trie樹（圖片出處不明，網上引用處太多~）
第一個性質：
從圖中也可以看出，根節點是/, 代表的內容也就是空，其他的節點比如，根節點下一個層級，有 h和s，分別代表的是兩個字符。
第二個性質：
從根節點到某一個節點，路徑上經過的字符連接起來，為該節點對應的字符串。
比如how表示的就是一個字符串，hi,也表示的是一個字符串，可是你會不會好奇，he和hel為什麼不能表示一個字符串呢？
當你想到這裡的話，說明你已經看得很仔細，馬上就要掌握它了，確實，從圖中看，我們會發現有些節點顏色不同，這是因為，我們預定好以這個深色的節點代表當前是一個字符串的結尾，想一想，這樣子的作用是啥？
那麼實際代碼中，我們應該如何去約定或者做個標記呢，其實只要設置一個標記位即可。
比如下面這樣子👇
const TrieNode = function () {
this.next = Object.create(null)
this.isEnd = false
};
當前的isEnd變量就表示當前的節點是不是結束串，當isEnd為True時，表示從根節點開始，到這個字符，所構成的字符串是存在的，是一個完整的字符串。
第三個性質：
每個節點的所有子節點包含的字符串不相同。
很明顯，我們從根節點開始，依次往下走，會發現，每個節點下面的節點是不相同的，所以依次組成的字符串不可能相同。
應用場景對Trie樹，有一定了解後，我們就可以看看它有哪些的實際應用場景了。
這裡參考的是網上所提供的幾個點👇
在搜尋引擎中關鍵詞提示，引擎會自動彈出匹配關鍵詞的下拉框，這種應用場景大家應該都很熟悉。
下拉框那麼應該如何利用一種高效的數據結構存儲呢，這裡就符合字典樹的性質，所以可以利用字典樹來構造特定的數據，達到一種更加快速檢索的效果。
字符串檢索
事先將已知的一些字符串（字典）的有關信息保存到trie樹裡，查找另外一些未知字符串是否出現過或者出現頻率，可以舉例子說明情況👇
1000萬字符串，其中有些是重複的，需要把重複的全部去掉，保留沒有重複的字符串。給出N 個單詞組成的熟詞表，以及一篇全用小寫英文書寫的文章，請你按最早出現的順序寫出所有不在熟詞表中的生詞。詞頻統計
給定很長的一個串，統計頻數出現次數最多情況，舉個例子👇
有一個1G大小的一個文件，裡面每一行是一個詞，詞的大小不超過16位元組，內存限制大小是1M。返回頻數最高的100個詞。一個文本文件，大約有一萬行，每行一個詞，要求統計出其中最頻繁出現的前10個詞，請給出思想，給出時間複雜度分析。字符串最長公共前綴
到現在，我們應該知道，Trie樹利用多個字符串的公共前綴來節省存儲空間，當我們把大量字符串存儲到一棵trie樹上時，我們可以快速得到某些字符串的公共前綴，所以可以利用這個特點來解決一些前綴問題。
非要舉個例子的話，有個例子👇
給出N 個小寫英文字母串，以及Q 個詢問，即詢問某兩個串的最長公共前綴的長度是多少？應用場景還是有很多的，剩下的可以自行去探索，接下來，我們通過實際的題目來看看，如何構造字典樹吧~
2個例子接下來，我們通過二個題目作為例子，來看看字典樹在實際應用可以解決哪些問題👇
詞典中最長的單詞⭐連結：詞典中最長的單詞
給出一個字符串數組words組成的一本英語詞典。從中找出最長的一個單詞，該單詞是由words詞典中其他單詞逐步添加一個字母組成。若其中有多個可行的答案，則返回答案中字典序最小的單詞。
若無答案，則返回空字符串。
示例 1：
輸入：
words = ["w","wo","wor","worl", "world"]
輸出："world"
解釋：
單詞"world"可由"w", "wo", "wor", 和 "worl"添加一個字母組成。
示例 2：
輸入：
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
輸出："apple"
解釋：
"apply"和"apple"都能由詞典中的單詞組成。但是"apple"的字典序小於"apply"。
提示：
來源：力扣（LeetCode）連結：https://leetcode-cn.com/problems/longest-word-in-dictionary著作權歸領扣網絡所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。
這題無非就是找到一個最長的單詞，可以拆分成words數組中某一部分，最暴力的思路就是去枚舉每一項，但是這樣子的時間複雜度是巨大的， 這個時候，我們是不是可以思考一下，這個問題有哪些地方是共性的呢？
沒錯，就是前綴是相同的，從這點來看，是不是就可以利用這個前綴樹，把它數據存儲下來然後遍歷一遍字典樹，只要這顆樹只有一個分支，則表示它有解，如果存在兩個分支以上的話，則無答案。複雜度分析
這點應該很好理解，這裡就跳過了。
這裡的話，我的解法構造字典樹，當然了，也有其他的解法，這裡就不展開了，可以看下我的代碼噢～
最長的串代碼點這裡☑️
其實你會發現，構造一個Trie樹的話，是很消耗空間的，有點空間換時間的意思，所以具體得根據實際的題目來解決問題。
實現Trie（前綴樹）⭐⭐連結：實現 Trie (前綴樹)
實現一個 Trie (前綴樹)，包含 insert, search, 和 startsWith 這三個操作。
示例:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 true
trie.search("app"); // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");
trie.search("app"); // 返回 true
說明:
你可以假設所有的輸入都是由小寫字母 a-z 構成的。來源：力扣（LeetCode）連結：https://leetcode-cn.com/problems/implement-trie-prefix-tree著作權歸領扣網絡所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。
這個題目就是典型的寫Trie樹，對於第一次寫這個題目的話，如果沒有思路的話，可以嘗試先看看別人的代碼，看看基本的套路在哪裡。
話不多說，可以參考這份代碼，可以看看如何構造一顆字典樹👇
leetcode-實現Trie樹代碼點這裡☑️
剩下的刪除操作，還有統計字符串出現的頻率，可以自己來實現一下，這個基本上不難，畫個圖，就知道如何實現啦～
題目是做不完的，做完這些題目後，希望你能對Trie字典樹有所認識，能對它有更加深入的理解~，接下來準備了四道題集，希望對你們有幫助~
詞典中最長的單詞
實現 Trie (前綴樹)
單詞搜索 II
Loading question
❤️ 感謝大家如果你覺得這篇內容對你挺有有幫助的話：
點讚支持下吧，讓更多的人也能看到這篇內容（收藏不點讚，都是耍流氓 -_-）關注公眾號前端UpUp，聯繫作者，遇到問題的話，歡迎打擾我，我們一起探討一起進步。歡迎聯繫作者噢，微信:DayDay2021,拉你進前端交流群。