Trie树(字典树，单词前缀树)
一、特点
由若干模式串构建而成。树中任一节点p，都对应于一个字符串S, S由从根出发走到p所经过的边上的字符构成，S是一个或多个模 式串的前缀。
任一模式串的前缀，都对应于树中的唯一节点
如图：
二、数据结构
struct trienode {
trienode * child[26] ; //假设所有字符就是26个小写字母
trienode() {
for(int i=0;i<26;i++){ child[i]=NULL; }
}
};
三、建树
void build(string s, trienode * root) {//参数为 插入到树中的字符串，根节点
trienode* p=root;
for (int i=0;i if (p->child[s[i]-’a’]== NULL) p->child[s[i] -’a’] = new trienode(); //初始化新的节点 p=p->child[s[i] -’a’]; } }//将n个模式串插入到一棵单词前缀树的时间复杂度为O(∑len(i)) ，其中len(i) 为第i个模式串的长度。 四、应用（图片来源网络） 应用 1. 自动补全 2. 拼写检查 3. IP 路由 (最长前缀匹配) 4. T9 (九宫格) 打字预测 图 4. T9（九宫格输入），在 20 世纪 90 年代常用于手机输入 5. 单词游戏