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”开头的单词）。
通过上面的例子，你会发现前缀树的核心是“共享前缀”和“标记结尾”。掌握了插入和查找的逻辑，就能轻松理解它在字典、搜索引擎、拼写检查等场景中的应用啦！