当前位置：首页 > article >正文

简单了解前缀树/字典树（Trie树）C++代码

article 2024/11/3 1:27:30

介绍Trie树

Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

前缀树也有一些其它的名称：字典树，前缀树，单词查找树等。

Trie树是一颗非典型的多叉树模型。

一般的多叉树，它们的结点通常主要包含了：

1.该结点的值

2.它的下一个孩子的指针

假设我们要查找的字符的范围是 [a,z]，也就是26的大小，

那么每一个前缀树的结点主要就包含以下两个值：

bool isEnd;
Trie* next[26];

第一个是一个bool值，它用来表示这个字符串是否到了结尾。

第二个值就是一个前缀树结点的指针的数组，它的大小刚好是26，那么这个结点的下一个孩子的指针数组下标就可以表示一个字符，而却并没有直接保存字符，这就是Trie树的巧妙之处。

比如，用如下的示意图可以表示字符串 aa aba ：

其它空指针就没有画出来了。并且它也可以表示字符串a ab，只要在对应的结点将isEnd改为true，表示它是一个字符串的末尾即可。

Trie树的简单实现

在力扣上有一道题：

这道题的大致意思就是让我们实现一个简单的前缀树，这个前缀树可以进行插入，查找，以及判断一个字符串是否是某个字符串的前缀。

代码：

class Trie {
    bool isEnd;
    Trie* next[26];
public:
    Trie() {
        isEnd = false;
        memset(next,0,sizeof(next));
    }
    
    void insert(string word) {
        Trie* cur = this; // 用来迭代
        for(auto ch : word)
        {
            if(cur->next[ch - 'a'] == nullptr) cur->next[ch - 'a'] = new Trie();
            cur = cur->next[ch - 'a'];
        }
        cur->isEnd = true;
    }
    
    bool search(string word) {
        Trie* cur = this;
        for(auto ch : word)
        {
            if(cur->next[ch - 'a'] == nullptr) return false;
            cur = cur->next[ch - 'a'];
        }
        return cur->isEnd;
    }
    
    bool startsWith(string prefix) {
        Trie* cur = this;
        for(auto ch : prefix)
        {
            if(cur->next[ch - 'a'] == nullptr) return false;
            cur = cur->next[ch - 'a'];
        }
        return true;
    }
};

这里的实现其实将结点和函数的实现放在一起了，也可以将结点在类外面进行封装。