目录
前缀树的定义
前缀树又称字典数树，Trie树（读作try），是哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计，也可用来做自动补全和拼写检查。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
常见应用
例如，在百度中搜索“为什么”，百度就会自动帮你补全一些常见的搜索问题。这些热词是怎么保存的呢？如果是用简单的线性表，就会需要大量重复的查找，效率较低；我们希望一个数据结构能够将相同前缀的字符串存放在一起，这样在查找的时候就可以快速取出了。
基本原理
它的原理非常简单，属于一看就会，一写就错的那种。如下图所示：例如我们有下列几个字符串：ad，ak，akp，akr和bp，我们如何构建前缀树呢？从根节点开始，比较字符串的每一个字符是否在树的当前节点有对应的边，如果有则路由到该边指向的下一节点，继续比较下一个字符。如ak节点：就是0->1->4对应的边组成；akr节点：就是0->1->4->7对应的边组成。可以看到所有的节点如果是字符串的末尾的字符都标为黑色，这是为了区分字符串前缀和字符串（如ak，既是字符串，又是akr和akp的前缀），在后面的代码上也有体现。
前缀树的主要操作是插入和查找，一般很少进行删除，即便是删除也是伪删除，即将一个变量置为删除，而不会释放其空间，这是因为物理上的删除将要改变前缀树已有的结构，牺牲性能。因此前缀树是一个只增不减的树。
如何实现
考虑实现该树的数据结构，首先要能保存当前节点的子节点的指针，建议使用指针数组来完成，例如要处理的是小写字母组成的字符，就可以用包含26个节点指针的数组。我们可以这样约定，如果某个字母存在，则指针数组对应的下标将指向该字母对应的节点，否则该下标的节点指向空。如字母c存在，则children[‘c’-‘a’] = next_ptr，否则children[‘c’-‘a’] = null。同时我们要能记录该节点是否是终节点，以区分字符串和字符串前缀，一个bool型变量即可。
vector<Trie*> children; // 指针数组
bool end; // 是否为终点
首先来考虑如何向前缀树中插入一个字符串：从根节点node开始，遍历node的26个子节点，如果节点存在，则node指向该子节点，考虑下一节点和下一个字符；如果节点不存在，则子节点指向一个新建的节点，并依次考虑下一字符和新建下一节点。可以用如下伪代码描述：
node = root
for i=0...word.size-1:
if node.children[word[i]-'a'] == null: // 没有该字符对应的节点，则新建节点
node.children[word[i]-'a'] = new node
node = node.children[word[i]-'a'] // 考察下一个节点和下一个字符
node.end = true // 最后一个字符设置为终点下来再来考虑如何判断一个字符或者字符前缀是否存在于树中：以判断前缀为例，只需要从根节点向下遍历，如果遇到某个字符对应的当前节点的下一节点不存在，则查找失败；直至遍历到最后一个字符，则查找成功。判断字符也是一样的操作，只不过最后要考虑最后一个节点的node.end是否为真。伪代码描述如下：
node = root
for i=0...word.size-1:
if node.children[word[i]-'a'] == null: // 没有该字符对应的节点，则返回失败
return false
node = node.children[word[i]-'a'] // 考察下一个节点和下一个字符
return true // 查找完全部字符，返回成功
代码验证
我们对Trie类的几个常用函数做进行如下假设：
-
Trie()
初始化前缀树对象。 -
void insert(String word)
向前缀树中插入字符串
word
。 -
boolean search(String word)
如果字符串
word
在前缀树中，返回
true
（即，在检索之前已经插入）；否则，返回
false
。 -
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false
具体实现，以c++为例，实现的函数一个类，可以使用leetcode验证：
208. 实现 Trie (前缀树)
class Trie {
private:
vector<Trie*> children; // 指针数组
bool end; // 是否为终点
public:
/*初始化节点*/
Trie() {
this->children = vector<Trie*>(26, NULL);
this->end = false;
}
/*插入函数*/
void insert(string word) {
// 从根节点开始
Trie* node = this;
// 遍历每一个字符和节点
for(int i=0; i<word.length(); i++){
// 不存在该节点则新建
if(node->children[word[i]-'a'] == NULL){
node->children[word[i]-'a'] = new Trie();
}
// 考察下一个节点
node = node->children[word[i]-'a'];
}
// 最后一个字符设置为终点
node->end = true;
}
/*查找字符串是否存在*/
bool search(string word) {
// 从根节点开始
Trie* node = this;
// 遍历每一个字符和节点
for(int i=0; i<word.length(); i++){
// 不存在该节点则失败
if(node->children[word[i]-'a'] == NULL){
return 0;
}
// 考察下一节点
node = node->children[word[i]-'a'];
}
// 注意：要为终点才是查找成功，否则只是字符串前缀
return node->end;
}
/*查找字符串前缀是否存在*/
bool startsWith(string prefix) {
// 从根节点开始
Trie* node = this;
// 遍历每一个字符和节点
for(int i=0; i<prefix.length(); i++){
// 不存在该节点则失败
if(node->children[prefix[i]-'a'] == NULL){
return 0;
}
// 考察下一节点
node = node->children[prefix[i]-'a'];
}
// 查找成功
return 1;
}
};