1. 什麼是前綴樹？¶
前綴樹（Trie Tree），也叫字典樹，是一種專門處理字符串前綴問題的數據結構。想象一下，如果你需要快速查找字典裏的單詞，或者做自動補全、拼寫檢查，用前綴樹會比普通數組/哈希表更高效。它的核心思想是：利用字符串的公共前綴節省空間，讓查找更快。比如存儲“apple”和“app”時，“app”的三個字母可以複用“apple”前三個字母的節點，不需要重複存儲。
2. 前綴樹的“節點”長什麼樣？¶
每個節點代表一個字符，主要包含三部分：
- 字符：當前節點存儲的字母（比如‘a’、‘p’等）。
- 子節點：最多包含26個子節點（假設處理小寫字母，每個子節點對應一個字母）。
- isEnd標記：布爾值，標記當前節點是否是某個單詞的結尾（比如“app”的結尾在第三個‘p’節點，需要標記爲true）。
3. 如何往前綴樹中“存”單詞？（插入操作）¶
以插入單詞“apple”爲例，步驟如下：
1. 從根節點開始：根節點沒有字符，是所有單詞的起點。
2. 逐個字符處理：
- 第一個字符‘a’：根節點的子節點中沒有‘a’，新建一個‘a’節點，當前指針移到‘a’節點。
- 第二個字符‘p’：‘a’節點的子節點中沒有‘p’，新建‘p’節點，指針移到‘p’節點。
- 第三個字符‘p’：當前‘p’節點的子節點中沒有‘p’，新建‘p’節點，指針移到‘p’節點。
- 第四個字符‘l’：當前‘p’節點的子節點中沒有‘l’，新建‘l’節點，指針移到‘l’節點。
- 第五個字符‘e’：當前‘l’節點的子節點中沒有‘e’，新建‘e’節點，指針移到‘e’節點。
3. 標記結尾：將‘e’節點的isEnd設爲true，表示“apple”在此結束。
4. 如何在前綴樹中“查”單詞？（查找操作）¶
以查找“apple”爲例，步驟如下：
1. 從根節點開始，逐個字符匹配：
- 第一個字符‘a’：根節點有‘a’子節點，指針移到‘a’節點。
- 第二個字符‘p’：‘a’節點有‘p’子節點，指針移到‘p’節點。
- 第三個字符‘p’：當前‘p’節點有‘p’子節點，指針移到‘p’節點。
- 第四個字符‘l’：當前‘p’節點有‘l’子節點，指針移到‘l’節點。
- 第五個字符‘e’：當前‘l’節點有‘e’子節點，指針移到‘e’節點。
2. 檢查結尾標記：處理完所有字符後，必須確認isEnd是否爲true。如果是，說明“apple”存在；如果不是（比如只是前綴），則不存在。
5. 實例講解：存儲與查找實戰¶
假設我們存儲了4個單詞：app、apple、banana、bat。
存儲過程（插入）：¶
- 插入“app”：
根→a→p→p（最後一個‘p’節點isEnd=true）。 - 插入“apple”：
根→a→p→p→l→e（最後一個‘e’節點isEnd=true）。 - 插入“banana”：
根→b→a→n→a→n→a（最後一個‘a’節點isEnd=true）。 - 插入“bat”：
根→b→a→t（最後一個‘t’節點isEnd=true）。
查找過程（驗證）：¶
- 查“app”：
根→a→p→p，檢查最後一個‘p’節點isEnd=true→存在。 - 查“apple”：
根→a→p→p→l→e，檢查最後一個‘e’節點isEnd=true→存在。 - 查“banana”：
根→b→a→n→a→n→a，檢查最後一個‘a’節點isEnd=true→存在。 - 查“bat”：
根→b→a→t，檢查最後一個‘t’節點isEnd=true→存在。 - 查“ball”：
根→b→a→？節點a的子節點是n（banana）和t（bat），沒有‘l’→不存在。
6. 爲什麼要用前綴樹？¶
- 空間更省：如果有多個單詞共享前綴（比如“app”和“apple”），前綴樹只需要存儲一次公共部分（“app”），節省重複空間。
- 查找更快：查找時間複雜度是O(n)（n爲單詞長度），比普通數組查找（O(n)）更高效，且前綴樹天然支持前綴查詢（比如查找所有以“app”開頭的單詞）。
通過上面的例子，你會發現前綴樹的核心是“共享前綴”和“標記結尾”。掌握了插入和查找的邏輯，就能輕鬆理解它在字典、搜索引擎、拼寫檢查等場景中的應用啦！