字典树（Trie树）用法及例子（一）

深藏阁楼爱情的钟 2022-08-08 11:53 65阅读 0赞

# 字典树（Trie）概述 #

字典树，又名Trie树。顾名思义，在字典中很好用。我们在查牛津词典时都是先按第一个字母找到以这个字母为首的单词所在的初始位置，在此位置的基础上，再按照第二个字母继续找。。。  
插一句，字符串的字典序也是这个意思，先按照第一个字母排序，第一个字母相同的情况下再按照第二个字母排序。  
字典树的数据结构图：  
![字典树][20150515204012560]  
注意：节点中的value并不存储字符，节点中的value按需使用。每个节点中的next数组存储26（如果只有小写字母的话）个next节点的地址。

# 例一 #

某个字符串在一堆字符串中出现的次数，或者一堆字符串中含有某个前缀的字符串的个数。

#include<iostream>
    #include<string>
    
    using namespace std;
    
    //表示next数组的长度，表示26个字母。如果字符串中有其他字符的话，应相应调整。
    //如果所有的字符串都是手机号的话，那就是10了
    const int MAX_NUM = 26;
    struct trieNode{
        int i;//按需使用，本例子中表示从头到本字符组成的前缀出现的次数
        struct trieNode *next[MAX_NUM];
    };
    
    trieNode* CreateTrieNode(){
        trieNode *p = new trieNode;
        p->i = 1;
        for(int i = 0; i < MAX_NUM; i++)
            p->next[i] = NULL;
        return p;
    }
    
    void InsertTrieTree(trieNode **root, string str){
        trieNode *p;
        if(*root == NULL){
            p = CreateTrieNode();
            *root = p;
        }
        else
            p = *root;
        int len = str.length();
        int k;
        for(int i = 0; i < len; i++){
            k = str.at(i) - 'a';
            if(p->next[k] != NULL)
                p->next[k]->i += 1;
            else
                p->next[k] = CreateTrieNode();
            p = p->next[k];
        }
    }
    
    int SearchTrieTree(trieNode **root, string str){
        trieNode *p;
        if(*root == NULL)
            return 0;
        p = *root;
        int k, len = str.length();
        for(int i = 0; i < len; i++){
            k = str.at(i) - 'a';
            if(p->next[k] == NULL)
                return 0;
            p = p->next[k];
        }
        return p->i;
    }
    
    int main(){
        trieNode *root = NULL;
        InsertTrieTree(&root, "checking");
        InsertTrieTree(&root, "check");
        InsertTrieTree(&root, "for");
        InsertTrieTree(&root, "checking");
        InsertTrieTree(&root, "program");
        InsertTrieTree(&root, "programmer");
        cout << SearchTrieTree(&root, "che") << endl;//输出3
        cout << SearchTrieTree(&root, "prog") << endl;//输出2
    }

还有一个例子在[http://blog.csdn.net/u010902721/article/details/45749745][http_blog.csdn.net_u010902721_article_details_45749745]

[20150515204012560]: /images/20220805/db6345dfc2cf461c8a2cf307c4a501f2.png
[http_blog.csdn.net_u010902721_article_details_45749745]: http://blog.csdn.net/u010902721/article/details/45749745