字典树（前缀树）（Trie）-C++简单实现

之前在刷 leetcode 的时候有遇到一道需要用到字典树的题目，具体是啥我给忘了，但是当时确实是第一次了解到字典树的概念，在初步了解后，并跟着别人的代码复现了一篇后就放下了。

今天的 leetcode 每日一题 ：添加与搜索单词 - 数据结构设计。

很基础的一道字典树的题目，借此机会我想来自己实现一次并复习一下。

字典树是什么

好比假设有b，abc，abd，bcd，abcd，efg，hii 这6个单词,那我们创建trie树就得到

上面是知乎博主 K-STEINS 的解释以及配图。原文：数据结构与算法：字典树（前缀树）

从上面可以发现字典树的特点。

• 从根节点开始到任何一个子节点都是唯一的一个字符序列。
• 在插入的字符的最后一个字符对应的节点有标记（途中的红点）。

比如途中插入 abd，从根节点先到 a，在从a的子节点中找到b，再找到d，然后d节点带有红点标记，意味着字典中存有abd 这一字符。

注：上一句叙述中找到某一节点，希望不会给你带来误解。因为上图，字符是在路径上，而不是在节点上，但并不影响理解。

特点

由此我们可以发现：

• 字典树的根节点不代表任何字母。它仅是一个起始点。
• 任何一个节点最多只有26个子节点。（因为英语中只有26个字母）

优点

它的优点有：

• **天然带有去重的功能，节省存储空间。**若存储同样的字符，可以在节点中加入一个count的属性，用来记录被插入的字符重复的次数。
• 支持动态查询。可以根据用户输入的字符的前缀，搜索出带有前缀的字符。（举个例子就是若字典树已经被插入了字符”apple“,那么在用户输入"app"的时候,字典树已经快速定位到了apple附近）

字典树详细的优点以及其与哈希表等数据集结构的比较，读者可以看看上面贴出的知乎的专栏，有简单的介绍。

我自己的一些理解

还是这幅图，实际上在理解字典树的基础思想之后，会发现实际上字典树的本质。

实际上整个字典树对于字符的插入，其归根结底是对待插入字符对应节点的标注，即图上的标红点。

如上面所述，每一个字符，无论是"apple",“hello”,“BeiJing”，都是一串字符序列，那么在字典树中从根节点往下搜索必定能找到某一个节点对应插入的字符。所以我们做的其实是，根据输入的字符序列，找到那个节点，并标注。

更简单直观一点，其实是对一个字符串的转换成一个链表，并将若干个链表进行合并。比如"does"与"done"，两个字符串若转换成两个链表，则前两个链表节点的内容是一样的，合并以后看作字典树，则'd'、'o',为同一个节点，而在'o'节点有两个指针分别指向 'e'与 'n'。

若以上对你产生困惑或者不解，我很抱歉，这一段可以看作我的胡思乱想、头脑风暴。

实现细节

插入字符串

对一个新的字符串，字典数从根节点开始，字符串从第一个字符开始，进行搜索当前节点有无当前字符，若无则新创建一个。再移动指针和下标到对应的子节点和下一个字符，一直到字符串的最后一个字符为止。
到了最后一个字符，将当前对应的节点TreNode 的 finish 属性置为true 即可。

搜索字符串

安装插入方法从根节点向下搜索即可，区别在于，途中若遇到空节点则证明字典树中无此字符串。
找到最后一个节点，判断其finish属性，为false 则也证明字典树中无此字符串。

删除字符串

我采用回溯的思想，借助递归找到最后的一个节点，从最后一个节点开始“删除”。
对于字典树而言，删除比较特殊。我们对于一个节点的删除主要执行以下操作：

• 判断他的finish属性是否为 true，若为true 则将其置 false。 （若为true，说明字典树中有这个字符串，反之没有）。这个操作主要针对字符串最后一个字符对应的节点。安装上面的说明，插入一个字符串，它最后一个字符对应的节点的 finish属性应该为true。
• 判断他的子节点是否全部为nullptr。若全为空，则从内存上删除这个节点是可以的，若不全为空，则证明这个节点也包含在其他的字符串中，我们选择什么也不做。这一步需要对每一个节点进行判断。

实现（c++）

首先基于上面对字典树的认识，我们需要先构建字典树的节点的数据结构 TrieNode。

TrieNode：

TrieNode 两个必备的属性应该是：

• 一个bool变量，用来标注它是否是一个字符的结尾。
• 指向子节点的指针数组。

class TrieNode
{public:TrieNode *children[26];		//指向子节点的指针数组。bool finish;				//标注它是否是一个字符的结尾。
public:TrieNode():finish(false)	//构造函数，初始化两个属性{for (int i = 0; i < 26; i++){children[i] = nullptr;}}~TrieNode()					//析构函数，回收子节点的空间{for (int i = 0; i < 26; i++){delete children[i];children[i] = nullptr;}}
};

Trie:

那么对于字典树 Trie , 其主要的两个功能即对 字符串的插入以及搜索。
2021年10月21日：对字符串的删除已更新。

class TrieNode {public:TrieNode* children[26];bool finish;public:TrieNode() : finish(false) {for (int i = 0; i < 26; i++) {children[i] = nullptr;}}~TrieNode() {for (int i = 0; i < 26; i++) {delete children[i];children[i] = nullptr;}}bool empty() {for (auto p : children) {if (p != nullptr) return false;}return true;}
};class Trie {private:TrieNode* trieHead;int del_node(TrieNode* node, string word);public:Trie() { trieHead = new TrieNode; }void insert(string word);void del(string word);bool search(string word);bool startsWith(string prefix);
};int Trie::del_node(TrieNode* node, string word) {int c = word[0] - 'a';if (word.size() == 1) {  // 最后一个节点if (node->children[c] == nullptr)return 0;  // 字典中和没有此字符串else {auto child_node = node->children[c];if (child_node->finish == true) {  //同时判断字典中有无此字符串if (child_node->empty() == true) {node->children[c] = nullptr;  // 现在节点中除去delete (child_node);          // 释放空间return 1;                     // del success} else {  // 有其他子节点， 不能释放 移除标记即可child_node->finish = false;return 1;  // del success}} else {return 0;  // 字典中没有此字符串}}} else {if (node->children[c] == nullptr) return 0;  // 无此字符if (del_node(node->children[c], word.substr(1, word.size() - 1)) ==true) {// 这部分删除的代码和上面删除的代码一样，懒得打包了。。。auto child_node = node->children[c];if (child_node->empty() == true) {node->children[c] = nullptr;  // 现在节点中除去delete (child_node);          // 释放空间return 1;                     // del success} else {  // 有其他子节点， 不能释放 移除标记即可child_node->finish = false;return 1;  // del success}} elsereturn 0;}
}void Trie::del(string word) {TrieNode* node = trieHead;del_node(node, word);
}void Trie::insert(string word) {TrieNode* node = trieHead;for (int i = 0; i < word.size(); i++) {int c = word[i] - 'a';if (node->children[c] == nullptr) node->children[c] = new TrieNode;node = node->children[c];}node->finish = true;
}bool Trie::search(string word) {TrieNode* node = trieHead;for (int i = 0; i < word.size(); i++) {int c = word[i] - 'a';if (node->children[c] == nullptr) return false;node = node->children[c];}return (node->finish == true) ? true : false;
}bool Trie::startsWith(string prefix) {TrieNode* node = trieHead;for (int i = 0; i < prefix.size(); i++) {int c = prefix[i] - 'a';if (node->children[c] == nullptr) return false;node = node->children[c];}return true;
}

最后贴出 208. 实现 Trie (前缀树)的链接。

能力有限，希望本文能对你有些许帮助😀。