Trie树也称字典树，因为其效率很高，所以在在字符串查找、前缀匹配等中应用很广泛，其高效率是以空间为代价的。利用串构建一个字典树，这个字典树保存了串的公共前缀信息，因此可以降低查询操作的复杂度。

下面以单词为例，插入、查找和删除实现

#define MaxN 26typedef struct TrieNode{    bool isStr; //标记是否构成单词    struct TrieNode *next[MaxN];}Trie;void InsertWords(Trie *root, const char *s){    if(root == NULL || *s == '\0')        return;    Trie *p = root;    while(*s != '\0')    {        if(p->next[*s-'a']==NULL)        {            Trie *temp = new Trie();            for(int i = 0; i< MaxN; i++)            {                temp->next[i] = NULL;            }            temp->isStr = false;            p->next[*s-'a'] = temp;            p = p->next[*s-'a'];        }        else        {            p = p->next[*s-'a'];        }        s++;    }    p->isStr = true;}int SearchWord(Trie *root, const char *s){    Trie *p = root;    while(p != NULL && *s != '\0')    {        p = p->next[*s-'a'];        s++;    }    return (p != NULL && p->isStr == true);}void delTrie(Trie *root){    for(int i = 0; i < MaxN; i++)    {        if(root->next[i] != NULL)            delTrie(root->next[i]);    }    delete root;}