C++如何实现一个Trie树(字典树)_C++高效处理字符串前缀查询的数据结构-C++-PHP中文网

C++如何实现一个Trie树(字典树)_C++高效处理字符串前缀查询的数据结构

冰火之心

发布： 2025-11-22 17:27:06

原创

249人浏览过

Trie树通过共享前缀存储字符串，支持高效插入、查找和前缀匹配，时间复杂度为O(L)，适用于自动补全、拼写检查等场景。

c++如何实现一个trie树(字典树)_c++高效处理字符串前缀查询的数据结构

在处理字符串前缀相关问题时，Trie树（字典树）是一种非常高效的数据结构。它通过共享前缀的方式存储字符串集合，能快速完成插入、查找和前缀匹配操作，时间复杂度为 O(L)，其中 L 是字符串长度。

基本原理与结构设计

Trie树的核心思想是将字符串按字符逐层分解，每个节点代表一个字符，从根到某节点的路径构成一个字符串前缀。常见实现方式是使用指针或数组构建多叉树结构。

每个节点包含：

子节点指针数组：通常用大小为26的指针数组对应 'a'-'z' 字符（也可用哈希表支持更多字符）
标记位 isEnd：表示是否为某个字符串的结尾

示例：插入 "apple" 后，根 → a → p → p → l → e，e 节点的 isEnd 为 true。

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

ClipDrop

Stability.AI出品的图片处理系列工具（背景移除、图片放大、打光）

112

查看详情

C++ 实现代码

以下是一个简洁且高效的 Trie 树实现：

#include <vector>
using namespace std;

class Trie {
private:
    struct TrieNode {
        vector<TrieNode*> children;
        bool isEnd;

        TrieNode() : children(26, nullptr), isEnd(false) {}
    };

    TrieNode* root;

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;
    }
};

登录后复制