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

字典树介绍以及C++实现

news 2025/7/17 22:48:21

字典树的概念

字典树（Trie），又称为前缀树或单词查找树，是一种树形数据结构，主要用于存储具有相同前缀的字符串集合。它特别适合用于词典中的单词查找、自动补全、拼写检查等应用。
在这里插入图片描述
字典树算法的核心思想就是每层存入单词的字符，顺着树节点依次往下排布，用bool judge变量来标记此字符处是否构成单词（某个单词的结尾字符），还可以用一个int counter变量来累计某个前缀出现的次数。

字典树的特点：

根节点不包含字符，通常为空。
每个节点表示一个字符串中的字符。
从根节点到某一节点的路径表示一个字符串。
每个节点的所有子节点包含的字符都不相同。

字典树的操作：

插入操作：将一个字符串逐字符插入字典树。对于每个字符，从根节点开始，检查是否存在对应的子节点。如果不存在，则创建一个新的节点。
查找操作：检查一个字符串是否在字典树中。类似于插入操作，逐字符检查是否存在对应的节点。
删除操作：从字典树中删除一个字符串。需要小心处理节点的删除，以确保不影响其他字符串的存储。

字典树的优点：

快速查找：查找的时间复杂度为O(m)，其中m为待查找字符串的长度。
节省空间：通过共享相同前缀的方式，节省了存储空间。

字典树的缺点：

空间消耗大：在最坏的情况下，字典树可能需要大量的节点和指针。
实现复杂性：相对于哈希表，字典树的实现相对复杂。

字典树在很多应用中表现出色，尤其是在需要处理大量字符串并进行快速查找的场景中。

C++代码实现字典树

在C++中实现字典树（Trie）通常包括以下几个步骤：

定义 TrieNode 类：每个节点包含若干子节点和一些必要的信息，比如标记是否是某个单词的结尾。
定义 Trie 类：主要提供插入、查找和删除等功能。

下面是一个简单的字典树（Trie）的C++实现：

1. 定义 `TrieNode` 类

#include <iostream>
#include <unordered_map>using namespace std;// TrieNode 节点结构
class TrieNode {
public:unordered_map<char, TrieNode*> children; // 子节点映射bool isEndOfWord;  // 是否是一个单词的结尾TrieNode() : isEndOfWord(false) {}
};

2. 定义 `Trie` 类

class Trie {
private:TrieNode* root;  // 根节点public:// 构造函数Trie() {root = new TrieNode();}// 插入一个单词到字典树void insert(const string& word) {currentNode = root;for (char c : word) {if (currentNode->children.find(c) == currentNode->children.end()) {currentNode->children[c] = new TrieNode();}currentNode = currentNode->children[c];}currentNode->isEndOfWord = true;  // 标记单词的结尾}// 查找一个单词是否存在于字典树中bool search(const string& word) {TrieNode* currentNode = root;for (char c : word) {if (currentNode->children.find(c) == currentNode->children.end()) {return false;  // 如果有任何字符找不到，返回 false}currentNode = currentNode->children[c];}return currentNode->isEndOfWord;  // 返回当前节点是否是单词的结尾}// 查找是否有任何单词以给定的前缀开始bool startsWith(const string& prefix) {TrieNode* currentNode = root;for (char c : prefix) {if (currentNode->children.find(c) == currentNode->children.end()) {return false;  // 如果前缀中的某个字符找不到，返回 false}currentNode = currentNode->children[c];}return true;  // 如果前缀存在，返回 true}
};

3. 使用字典树

int main() {Trie trie;// 插入单词trie.insert("apple");trie.insert("app");trie.insert("banana");// 查找单词cout << "search(\"apple\"): " << trie.search("apple") << endl;   // 输出 1 (true)cout << "search(\"app\"): " << trie.search("app") << endl;       // 输出 1 (true)cout << "search(\"banana\"): " << trie.search("banana") << endl; // 输出 1 (true)cout << "search(\"bat\"): " << trie.search("bat") << endl;       // 输出 0 (false)// 查找前缀cout << "startsWith(\"app\"): " << trie.startsWith("app") << endl;  // 输出 1 (true)cout << "startsWith(\"ban\"): " << trie.startsWith("ban") << endl;  // 输出 1 (true)cout << "startsWith(\"bana\"): " << trie.startsWith("bana") << endl;  // 输出 1 (true)cout << "startsWith(\"cat\"): " << trie.startsWith("cat") << endl;  // 输出 0 (false)return 0;
}

4. 代码解析

TrieNode 类：
- 使用 unordered_map 存储子节点映射，unordered_map 是 C++ 中一个哈希表实现，用来存储每个字符对应的子节点。
- isEndOfWord 用来标记当前节点是否是某个单词的结尾。
Trie 类：
- insert：通过遍历单词的每个字符，将它们插入到字典树中。如果字符不存在，就创建新的节点。最后标记该节点为单词的结尾。
- search：查找一个单词是否在字典树中。如果路径上的任何字符不存在，直接返回 false。最终检查最后一个节点是否是单词的结尾。
- startsWith：查找是否有任何单词以给定前缀开始。只要能够找到前缀的所有字符，就返回 true。

5. 输出示例：

search("apple"): 1
search("app"): 1
search("banana"): 1
search("bat"): 0
startsWith("app"): 1
startsWith("ban"): 1
startsWith("bana"): 1
startsWith("cat"): 0