Trie树（字典树）_字典树(trie tree)

trie树，又称字典树或前缀树，是一种有序 的、用于统计、排序和存储字符串的数据 结构，它与二叉查找树不同，关键字不是 直接保存在节点中，而是由节点在树中的 位置决定。 一个节点的所有子孙都有相同的前缀，也 就是这个节点对应的字符串，而根节点对 应空字符串。一般情况下，不是所有的节点 都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。 trie树的最大优点就是利用字符串的公共前 缀来减少存储空间与查询时间，从而最大 限度地减少无谓的字符串比较，是非常高 效的字符串查找数据结构。

深度遍历

深度搜索trie树，对于正在搜索的节点node: 遍历该节点的26个孩子指针child[i]('a'-'z')，如果指针不空:

将该child[i]对应的字符(i+’a’)，push进入栈中， 如果该孩子指针标记的is_end为真(说明这个位置是一个单词):

从栈底到栈顶对栈进行遍历，生成字符串，将它保存到结果数组中 深度搜索child[i]

弹出栈顶字符

Trie树的单词插入：

Trie树的单词搜索

#include <iostream>
#include<vector>
#define TRIE_MAX_CHAR_NUM 26
struct TrieNode{
    struct TrieNode * child[TRIE_MAX_CHAR_NUM];
    bool is_end;
    TrieNode() : is_end(false){
        for(int i=0;i< TRIE_MAX_CHAR_NUM;i++){
            child[i] = 0;
        }
    }
};
 
class TrieTree{
public:
    TrieTree(){
        
    }
    ~TrieTree(){//定义析构函数
        for(int i=0;i<_node_vec.size();i++){
            delete _node_vec[i];
        }
    }
    void insert(const char *word){
        TrieNode *ptr = &_root;
        while(*word){
            int pos = *word - 'a';
            if(!ptr->child[pos]){
                ptr->child[pos] = new_node();
            }
            ptr = ptr->child[pos];
            word++;
        }
        ptr->is_end = true;
    }
    bool startsWith(const char *prefix){
        TrieNode *ptr = &_root;
        while(*prefix){
            int pos = *prefix - 'a';
            if(!ptr->child[pos]){
                return false;
            }
            ptr = ptr->child[pos];
            prefix++;
        }
        return true;
    }
    bool search(const char *word){
        TrieNode *ptr = &_root;
        while(*word){
            int pos = *word - 'a';
            if(!ptr -> child[pos]){
                return false;
            }
            ptr = ptr->child[pos];
            word++;
        }
        return ptr->is_end;
    }
    TrieNode *root(){
        return &_root;
    }
    
private:
    TrieNode *new_node(){
        TrieNode *node = new TrieNode();
        _node_vec.push_back(node);
        return node;
    }
    std::vector<TrieNode *> _node_vec;
    TrieNode _root;
};
 
void preorder_trie(TrieNode *node,int layer){
    for(int i=0;i<TRIE_MAX_CHAR_NUM;i++){
        if(node->child[i]){
            for(int j=0;j<layer;j++){
                printf("---");
            }
            printf("%c",i+'a');
            if(node->child[i]->is_end){
                printf("(end)");
            }
            printf("\n");
            preorder_trie(node->child[i],layer+1);
        }
    }
}
 
void get_all_word_from_trie(TrieNode *node,std::string &word,
                            std::vector<std::string> &word_list){
    for(int i=0;i<TRIE_MAX_CHAR_NUM;i++){
        if(node->child[i]){
            word.push_back(i+'a');//将字符入栈
            if(node->child[i]->is_end){
                word_list.push_back(word);
            }
            get_all_word_from_trie(node->child[i],word,word_list);
            word.erase(word.length()-1,1);//弹出栈顶字符
        }
    }
}
 
int main(int argc, const char * argv[]) {
    TrieTree trie_tree;
    trie_tree.insert("abcd");
    trie_tree.insert("abc");
    trie_tree.insert("abd");
    trie_tree.insert("b");
    trie_tree.insert("bcd");
    trie_tree.insert("efg");
    preorder_trie(trie_tree.root(), 0);
    printf("\n");
    std::vector<std::string> word_list;
    std::string word;
    printf("All words:\n");
    get_all_word_from_trie(trie_tree.root(),word,word_list);
    for(int i=0;i<word_list.size();i++){
        printf("%s\n",word_list[i].c_str());
    }
    printf("\n");
    printf("Search:\n");
    printf("abc:%d\n",trie_tree.search("abc"));
    printf("abcd:%d\n",trie_tree.search("abcd"));
    printf("bc:%d\n",trie_tree.search("bc"));
    printf("b:%d\n",trie_tree.search("b"));
    printf("\n");
    printf("ab:%d\n",trie_tree.startsWith("ab"));
    printf("abc:%d\n",trie_tree.startsWith("abc"));
    printf("bc:%d\n",trie_tree.startsWith("bc"));
    printf("fg:%d\n",trie_tree.startsWith("fg"));
    
    
 
    return 0;
}

输出：

a
---b
------c(end)
---------d(end)
------d(end)
b(end)
---c
------d(end)
e
---f
------g(end)
 
All words:
abc
abcd
abd
b
bcd
efg
 
Search:
abc:1
abcd:1
bc:0
b:1
 
ab:1
abc:1
bc:1
fg:0
Program ended with exit code: 0