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

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

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

定义Trie节点结构

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

struct TrieNode {
    TrieNode* children[26]; // 假设只处理小写字母 a-z
    bool isEnd;
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;
}
实现前缀搜索
搜索分为两种：完整单词匹配和前缀判断。

							

								
								

									居然设计家
									
居然之家和阿里巴巴共同打造的家居家装AI设计平台
								
								下载 
							
						
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 
#include 
using namespace std;
struct TrieNode {
TrieNode* children[26];
bool isEnd;
TrieNode() : isEnd(false) {
for (int i = 0; i < 26; ++i) children[i] = nullptr;
}
};
class Trie {
public:
Trie() {
root = new TrieNode();
}
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 apple") 
基本上就这些。通过维护字符路径和结束标记，Trie能以 O(n) 时间完成插入和搜索，n为字符串长度，非常适合高频查询场景。