Trie树，又叫字典树、前缀树（Prefix Tree）、单词查找树 或 键树，是一种多叉树结构。
此图是一棵Trie树，表示了关键字集合{“hers”, “his”, “she”, “i”, “he”} 。从图中可以看出： 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。 从根节点到标记呈橙色节点路径上字符组成的字符串是一个关键字。图中橙色节点就是关键字节点。 有共同前缀关键字有共同路径。 构建字典树 如果我们以英文小写字母作为字符集，那么每个节点都有26个分支子节点。由于有些节点是标志着一个插入字符串的结尾，所以需要有一个标记位判断是否是一个关键字。 我们定义根节点的结构如下：
struct Node
{
bool isKey; // 标记该节点是否代表一个关键字
Node * children[26]; // 各个子节点
};
刚开始字典树是只有一个根节点的。
Node* root = new Node();
我们需要通过一条一条加入字符串构建字典树。 插入一条字符串的过程：
void insert(string word) {
Node* t = root;
for (int i=0; i<word.size(); i++) {
int s = word[i]-'a';//得到数组下标
if (t->child[s] == NULL) {
t->child[s] = new Node();
}
t = t->child[s];
}
t->isKey = true;
}
Trie树的应用
字符串检索 检索/查询功能是Trie树最原始的功能。思路就是从根节点开始一个一个字符进行比较： 如果沿路比较，发现不存在的字符，则表示该字符串在集合中不存在。 如果所有的字符全部比较完并且全部相同，还需判断最后一个节点的标志位
struct Node
{
bool isKey; // 标记该节点是否代表一个关键字
Node * children[26]; // 各个子节点
};
词频统计 Trie树常被搜索引擎系统用于文本词频统计 。
struct Node
{
bool isKey; // 标记该节点是否代表一个关键字
Node * children[26]; // 各个子节点
};
思路：为了实现词频统计，我们修改了节点结构，用一个整型变量count来计数。对每一个关键字执行插入操作，若已存在，计数加1，若不存在，插入后count置1。
字符串排序 Trie树可以对大量字符串按字典序进行排序，思路也很简单：遍历一次所有关键字，将它们全部插入trie树，树的每个结点的所有儿子很显然地按照字母表排序，然后先序遍历输出Trie树中所有关键字即可。
前缀匹配 例如：找出一个字符串集合中所有以ab开头的字符串。我们只需要用所有字符串构造一个trie树，然后输出以a->b->开头的路径上的关键字即可。 trie树前缀匹配常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能。
作为其他数据结构和算法的辅助结构 如后缀树，AC自动机等。
字符串检索的Trie树代码
class Trie {
public:
struct Node {
bool isKey;//是否当前节点作为一个单词的结尾
Node* child[26];//a-z
} *head;
/** Initialize your data structure here. */
Trie() {
head = new Node();
}
/** Inserts a word into the trie. */
void insert(string word) {
Node* t = head;
for (int i=0; i<word.size(); i++) {
int s = word[i]-'a';
if (t->child[s] == NULL) {
t->child[s] = new Node();
}
t = t->child[s];
}
t->isKey = true;
}
/** Returns if the word is in the trie. */
bool search(string word) {
Node* t = head;
for (int i=0; i<word.size(); i++) {
int s = word[i] - 'a';
if (t->child[s] == NULL) return false;
t = t->child[s];
}
return t->isKey;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
Node* t = head;
for (int i=0; i<prefix.size(); i++) {
int s = prefix[i] - 'a';
if (t->child[s] == NULL) return false;
t = t->child[s];
}
return true;
}
};
用数组作为trie的储存结构。 数组下表起到指针的作用，new 一个节点得到的指针就是将当前树的大小作为指针, 因为sz是树中节点的个数(包括根节点)，而节点的编号是从0开始，所以树中存在编号0到sz-1刚好sz个，此时若分配新节点刚好是sz作为编号。
// Trie
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXN 1000005
#define SIGMA 26
//仅含小写英文字母
using namespace std;
namespace Trie {
int tr[MAXN][SIGMA];//数组存储Trie树节点,下标起到指针作用
int val[MAXN];//若当前节点不是一个模式串的结尾则为0
int sz;//Trie中当前节点个数
Trie() {
memset(tr, 0, sizeof(tr));
memset(val, 0, sizeof(val));
sz = 1;
}
//插入
void insert(char* s) {
int len = strlen(s), u = 0;
for (int i=0; i<len; i++) {
if (tr[u][s[i]-'a'] == 0) {//不存在新开就一个节点
tr[u][s[i]-'a'] = sz;
sz++;
}
u = tr[u][s[i]-'a'];
}
val[u] = 1;
}
//查询s是否存在
bool query(char* s) {
int len = strlen(s), u = 0;
for (int i=0; i<len; i++) {
if (tr[u][s[i]-'a'] == 0) return false;
u = tr[u][s[i]-'a'];
}
return val[u];
}
};
char txt[100];
char pat[5][100] = {"hers", "he", "his", "she", "i"};
int main() {
Trie::Trie();
for (int i=0; i<5; i++) {
Trie::insert(pat[i]);
}
while (1) {
cin >> txt;
cout << Trie::query(txt) << endl;
}
return 0;
}