c++中如何实现前缀树搜索_c++前缀树搜索实现方法-C++-PHP中文网

c++中如何实现前缀树搜索_c++前缀树搜索实现方法

穿越時空

发布： 2025-09-25 20:11:01

原创

879人浏览过

前缀树通过构建字符路径实现高效字符串存储与检索。1. 定义TrieNode结构，包含26个子节点指针和isEnd标志位；2. 插入时逐字符创建节点并标记结尾；3. 搜索时遍历路径，完整匹配需isEnd为真；4. 前缀判断只需路径存在。C++实现支持O(n)时间复杂度的插入与查询，适用于自动补全等场景。

c++中如何实现前缀树搜索_c++前缀树搜索实现方法

前缀树（Trie）是一种用于高效存储和检索字符串的树形数据结构，特别适合实现字符串前缀匹配、自动补全、拼写检查等功能。在C++中实现前缀树搜索，核心是构建Trie节点结构，并实现插入与搜索操作。

定义Trie节点结构

每个Trie节点包含一个指向子节点的数组（或map），以及一个标志位表示是否为某个字符串的结尾。

struct TrieNode {
    TrieNode* children[26]; // 假设只处理小写字母 a-z
    bool isEnd;
<pre class='brush:php;toolbar:false;'>TrieNode() {
    for (int i = 0; i < 26; i++) {
        children[i] = nullptr;
    }
    isEnd = false;
}

登录后复制

};

插入字符串到Trie

从根节点开始，对字符串中的每个字符，检查对应子节点是否存在，不存在则创建新节点。遍历完所有字符后，标记最后一个节点为单词结尾。

立即学习“C++免费学习笔记（深入）”；

void insert(TrieNode* root, const string& word) {
    TrieNode* node = root;
    for (char c : word) {
        int idx = c - 'a';
        if (!node->children[idx]) {
            node->children[idx] = new TrieNode();
        }
        node = node->children[idx];
    }
    node->isEnd = true;
}

登录后复制

实现前缀搜索

搜索分为两种：完整单词匹配和前缀判断。

MacsMind

电商AI超级智能客服

131

查看详情

1. 搜索完整单词：逐字符匹配路径，最终节点必须存在且 isEnd 为 true。

bool search(TrieNode* root, const string& word) {
    TrieNode* node = root;
    for (char c : word) {
        int idx = c - 'a';
        if (!node->children[idx]) {
            return false;
        }
        node = node->children[idx];
    }
    return node->isEnd;
}

登录后复制

2. 判断是否存在某前缀：只需路径存在，无需 isEnd 标志。

bool startsWith(TrieNode* root, const string& prefix) {
    TrieNode* node = root;
    for (char c : prefix) {
        int idx = c - 'a';
        if (!node->children[idx]) {
            return false;
        }
        node = node->children[idx];
    }
    return true;
}

登录后复制

完整使用示例

将上述部分组合成可运行代码：

#include <iostream>
#include <string>
using namespace std;
<p>struct TrieNode {
TrieNode* children[26];
bool isEnd;
TrieNode() : isEnd(false) {
for (int i = 0; i < 26; ++i) children[i] = nullptr;
}
};</p><p>class Trie {
public:
Trie() {
root = new TrieNode();
}</p><pre class='brush:php;toolbar:false;'>void insert(const string& word) {
    TrieNode* node = root;
    for (char c : word) {
        int idx = c - 'a';
        if (!node->children[idx]) {
            node->children[idx] = new TrieNode();
        }
        node = node->children[idx];
    }
    node->isEnd = true;
}

bool search(const string& word) {
    TrieNode* node = root;
    for (char c : word) {
        int idx = c - 'a';
        if (!node->children[idx]) return false;
        node = node->children[idx];
    }
    return node->isEnd;
}

bool startsWith(const string& prefix) {
    TrieNode* node = root;
    for (char c : prefix) {
        int idx = c - 'a';
        if (!node->children[idx]) return false;
        node = node->children[idx];
    }
    return true;
}

登录后复制

private: TrieNode* root; };

// 使用示例 int main() { Trie trie; trie.insert("apple"); cout << trie.search("apple") << endl; // 输出 1 (true) cout << trie.search("app") << endl; // 输出 0 (false) cout << trie.startsWith("app") << endl; // 输出 1 (true) trie.insert("app"); cout << trie.search("app") << endl; // 输出 1 (true) return 0; }

基本上就这些。通过维护字符路径和结束标记，Trie能以 O(n) 时间完成插入和搜索，n为字符串长度，非常适合高频查询场景。

以上就是c++++中如何实现前缀树搜索_c++前缀树搜索实现方法的详细内容，更多请关注php中文网其它相关文章！