字典树

字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

----摘自必应

其建立过程类似链表的生成，顾名思义，每次我们查询、插入一个单词，都从单词首字母开始，查看本节点内是否存在指向下一字母的指针，依次向后查找字典树。在结构体里还可以存放其他变量，使得查找到单词时可以输出和单词对应的数据。

插入、查找过程见代码详解。

注意：G++提交字典树题目容易MLE，请用C++提交。

模板

#include <iostream>
#include <string>
using namespace std;
struct Node
{
    Node *ap[26];//保存指向下一节点的指针
    //---
    //存放每个单词的一些属性，数据类型根据需求自定，或者使用结构体保存
    int num;//保存出现次数
    //---
    void ini()//生成新节点时调用对其初始化
    {
        num=0;
        for(int i=0;i<26;i++)
            ap[i]=NULL;
    }
}*head;//申明头指针用于指向字典树
void Insert(string str)
{
    Node *now=head,*makeNode;//now指针用于指向当前位置，makeNode用于生成新节点，再让now->ap[odx]指向新生成的节点
    for(int i=0;i<str.length();i++)
    {
        int odx=str[i]-'a';
        if(now->ap[odx]==NULL)//如果为空说明字典树没有后续的内容，就建立新节点
        {
            makeNode=new Node;
            makeNode->ini();
            now->ap[odx]=makeNode;
        }
        now=now->ap[odx];//迭代now指针，使其转移到下一位置
    }
    now->num++;
}
bool Find(string str)//返回值根据要求而定
{
    int counter=0;
    Node *now=head;
    for(int i=0;i<str.length();i++)//迭代过程类似插入
    {
        int odx=str[i]-'a';
        counter=now->num;
        if(now->ap[odx]==NULL)
            return false;
        now=now->ap[odx];
    }
    return true;
}
void del(Node *root)
{
    if(root==NULL)
        return;
    for(int i=0;i<26;i++)
        del(root->ap[i]);
    delete root;
}