> For the complete documentation index, see [llms.txt](https://data-structure-and-algorithm.gitbook.io/project/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://data-structure-and-algorithm.gitbook.io/project/shu/qian-zhui-shu-zi-dian-shu.md).

# 前缀树（字典树）

### 概念解释

**前缀树(Prefix Trees或者Trie)**与树类似，用于处理字符串相关的问题时非常高效。它可以实现快速检索，常用于字典中的单词查询，搜索引擎的自动补全甚至IP路由。

下图展示了“top”, “thus”和“their”三个单词在前缀树中如何存储的：

[![](https://blog.fundebug.com/2018/08/27/code-interview-data-structure/tries.png)](https://blog.fundebug.com/2018/08/27/code-interview-data-structure/tries.png)

单词是按照字母从上往下存储，“p”, “s”和“r”节点分别表示“top”, “thus”和“their”的单词结尾。

### **常见的树代码面试题**

* [统计前缀树表示的单词个数](https://www.geeksforgeeks.org/counting-number-words-trie/)
* [使用前缀树为字符串数组排序](https://www.geeksforgeeks.org/sorting-array-strings-words-using-trie/)