# 前缀树（字典树）

### 概念解释

**前缀树(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/)