Trie树。也称为字典数，前缀树，每一个单词的每一个字母依照顺序相应一个节点。有重合的前缀就共享节点。
理想情况下（满的情况）。假若全部的单词都是N长，则树共同拥有N层，每层都是26个子节点。
在程序上，将根节点编号为0，根节点不代表不论什么字符。
在程序的实现上，树能够用数组存储，也能够用指针实现。这里介绍简单的数组方法实现。
用一个child[i][j]保存节点i的编号为j的子节点序号，j相应26个字母。假设child[i][0] == 0，那么说明i节点以下没有a这个子节点。trie树中能够用 value[i]存储附加信息
附代码，參考刘汝佳大白书
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
using namespace std;
#define MAX_NODE 20000
#define sigma_size 26
struct Trie{
int child[MAX_NODE][sigma_size];
int value[MAX_NODE];
int size;
Trie(){
size = 1;
memset(child[0], 0, sizeof(child[0]));
}
int idx(char ch){
return ch - 'a';
}
void Insert(char *str, int val){
int u = 0, num = strlen(str);
for(int i = 0; i < num; i++){
int ch = idx(str[i]);
if(!child[u][ch]){
memset(child[size], 0, sizeof(child[size]));
value[size] = 0;
child[u][ch] = size++;
}
u = child[u][ch];
}
value[u] = val;
}
int Query(char *str){
int u = 0, num = strlen(str);
for(int i = 0; i < num; i++){
int ch = idx(str[i]);
if(child[u][ch]){
u = child[u][ch];
}
else{
return 0;
}
}
return 1;
}
};
int main(){
Trie tree;
tree.Insert("sun",0);
tree.Insert("yan",0);
tree.Insert("sin",0);
cout<<tree.Query("sun");
return 0;
}