Trie前缀树——数据结构系列教程(c++版)

5.1 Entitys.h 头文件

#ifndef ENTITYS_H_INCLUDED
#define ENTITYS_H_INCLUDED

#include <string>
#include <vector>

//************************************************************************************************************************************************************************
//                                                                      自定义类型
//************************************************************************************************************************************************************************

//========================================================================================================================================================================
//                                                                    学生结构体(Student)
//========================================================================================================================================================================
struct Student {
    int id;// 学号
    std::string name;// 姓名
    std::string dob;// 出生日期
    std::string sex;// 性别
    std::string gender;// 民族
    std::string address;// 地址
    float score;// 入学总分
    std::string school;// 学校
    std::string team;// 班级
    std::string status;// 状态

    bool operator<(const Student& other) const { return id < other.id; }
    bool operator>(const Student& other) const { return id > other.id; }
    bool operator==(const Student& other) const { return id == other.id; }
    bool operator!=(const Student& other) const { return id != other.id; }

    friend std::ostream& operator<<(std::ostream& os, const Student& s) {
        os << "[" << s.id<< ", " << s.name << ", " << s.dob << ", " << s.sex << ", " << s.gender  << ", " << s.address << ", " << s.score<< ", " << s.school<< ", " << s.team<< ", " << s.status << "]";
        return os;
    }
};

#endif // ENTITYS_H_INCLUDED
                    

5.2 Trie.h 头文件

#ifndef TRIE_H_INCLUDED
#define TRIE_H_INCLUDED

#include <iostream>
#include <string>
#include <vector>

//========================================================================================================================================================================
//                                                                    Trie节点结构体(TrieNode)
//========================================================================================================================================================================
struct TrieNode {
    TrieNode* children[26];  // 子节点数组：26个元素，对应a-z
    bool is_end;             // 标记是否是单词结尾
    int count;               // 单词出现次数

    // 构造函数
    TrieNode() : is_end(false), count(0) {
        for (int i = 0; i < 26; ++i) {
            children[i] = nullptr;
        }
    }

    // 析构函数：递归释放子节点
    ~TrieNode() {
        for (int i = 0; i < 26; ++i) {
            if (children[i] != nullptr) {
                delete children[i];
                children[i] = nullptr;
            }
        }
    }
};

//========================================================================================================================================================================
//                                                                    带权重Trie节点结构体(WeightedTrieNode)
//========================================================================================================================================================================
struct WeightedTrieNode {
    WeightedTrieNode* children[26];
    bool is_end;
    int weight; // 单词权重

    WeightedTrieNode() : is_end(false), weight(0) {
        for (int i = 0; i < 26; ++i) {
            children[i] = nullptr;
        }
    }

    ~WeightedTrieNode() {
        for (int i = 0; i < 26; ++i) {
            if (children[i] != nullptr) {
                delete children[i];
            }
        }
    }
};

//========================================================================================================================================================================
//
//                                                                 Trie树类(Trie)
//
//========================================================================================================================================================================
class Trie {
private:
    TrieNode* root; // 根节点

    // 递归删除辅助函数
    bool removeHelper(TrieNode* node, const std::string& word, int idx);
    // 打印所有单词辅助函数
    void printAllWordsHelper(TrieNode* node, std::string& path);

public:
    // 构造函数
    Trie();

    // 析构函数
    ~Trie();

    // 核心操作
    void insert(const std::string& word);       // 插入单词
    bool search(const std::string& word);       // 查询单词是否存在
    bool startsWith(const std::string& prefix); // 查询前缀是否存在
    bool remove(const std::string& word);       // 删除单词
    int getCount(const std::string& word);      // 获取单词出现次数
    void printAllWords();                       // 打印所有单词
};

//========================================================================================================================================================================
//
//                                                                 带权重Trie树类(WeightedTrie)
//
//========================================================================================================================================================================
class WeightedTrie {
private:
    WeightedTrieNode* root;

public:
    // 构造函数
    WeightedTrie();

    // 析构函数
    ~WeightedTrie();

    // 插入单词并设置权重
    void insert(const std::string& word, int weight);

    // 查询单词权重
    int getWeight(const std::string& word);

    // 查询单词是否存在
    bool search(const std::string& word);
};

#endif // TRIE_H_INCLUDED

5.3 Trie.cpp 程序代码

#include "Trie.h"

//========================================================================================================================================================================
//
//                                                                 Trie树类实现
//
//========================================================================================================================================================================

// 构造函数
Trie::Trie() {
    root = new TrieNode();
}

// 析构函数
Trie::~Trie() {
    delete root;
    root = nullptr;
}

// 插入单词
void Trie::insert(const std::string& word) {
    TrieNode* curr = root;
    for (char c : word) {
        int idx = c - 'a';
        if (curr->children[idx] == nullptr) {
            curr->children[idx] = new TrieNode();
        }
        curr = curr->children[idx];
    }
    curr->is_end = true;
    curr->count++;
}

// 查询单词是否存在
bool Trie::search(const std::string& word) {
    TrieNode* curr = root;
    for (char c : word) {
        int idx = c - 'a';
        if (curr->children[idx] == nullptr) {
            return false;
        }
        curr = curr->children[idx];
    }
    return curr->is_end;
}

// 查询前缀是否存在
bool Trie::startsWith(const std::string& prefix) {
    TrieNode* curr = root;
    for (char c : prefix) {
        int idx = c - 'a';
        if (curr->children[idx] == nullptr) {
            return false;
        }
        curr = curr->children[idx];
    }
    return true;
}

// 递归删除辅助函数
bool Trie::removeHelper(TrieNode* node, const std::string& word, int idx) {
    if (idx == word.size()) {
        if (!node->is_end) return false;
        node->is_end = false;
        node->count--;
        for (int i = 0; i < 26; ++i) {
            if (node->children[i] != nullptr) return false;
        }
        return true;
    }

    int c_idx = word[idx] - 'a';
    if (node->children[c_idx] == nullptr) return false;

    bool can_delete = removeHelper(node->children[c_idx], word, idx + 1);

    if (can_delete) {
        delete node->children[c_idx];
        node->children[c_idx] = nullptr;

        if (!node->is_end) {
            for (int i = 0; i < 26; ++i) {
                if (node->children[i] != nullptr) return false;
            }
            return true;
        }
    }

    return false;
}

// 删除单词
bool Trie::remove(const std::string& word) {
    return removeHelper(root, word, 0);
}

// 获取单词出现次数
int Trie::getCount(const std::string& word) {
    TrieNode* curr = root;
    for (char c : word) {
        int idx = c - 'a';
        if (curr->children[idx] == nullptr) {
            return 0;
        }
        curr = curr->children[idx];
    }
    return curr->is_end ? curr->count : 0;
}

// 打印所有单词辅助函数
void Trie::printAllWordsHelper(TrieNode* node, std::string& path) {
    if (node->is_end) {
        std::cout << path << " ";
    }

    for (int i = 0; i < 26; ++i) {
        if (node->children[i] != nullptr) {
            path.push_back('a' + i);
            printAllWordsHelper(node->children[i], path);
            path.pop_back();
        }
    }
}

// 打印所有单词
void Trie::printAllWords() {
    std::string path;
    printAllWordsHelper(root, path);
    std::cout << std::endl;
}

//========================================================================================================================================================================
//
//                                                                 带权重Trie树类实现
//
//========================================================================================================================================================================

// 构造函数
WeightedTrie::WeightedTrie() {
    root = new WeightedTrieNode();
}

// 析构函数
WeightedTrie::~WeightedTrie() {
    delete root;
}

// 插入单词并设置权重
void WeightedTrie::insert(const std::string& word, int weight) {
    WeightedTrieNode* curr = root;
    for (char c : word) {
        int idx = c - 'a';
        if (curr->children[idx] == nullptr) {
            curr->children[idx] = new WeightedTrieNode();
        }
        curr = curr->children[idx];
    }
    curr->is_end = true;
    curr->weight = weight;
}

// 查询单词权重
int WeightedTrie::getWeight(const std::string& word) {
    WeightedTrieNode* curr = root;
    for (char c : word) {
        int idx = c - 'a';
        if (curr->children[idx] == nullptr) {
            return -1;
        }
        curr = curr->children[idx];
    }
    return curr->is_end ? curr->weight : -1;
}

// 查询单词是否存在
bool WeightedTrie::search(const std::string& word) {
    WeightedTrieNode* curr = root;
    for (char c : word) {
        int idx = c - 'a';
        if (curr->children[idx] == nullptr) {
            return false;
        }
        curr = curr->children[idx];
    }
    return curr->is_end;
}

5.4 main.cpp 测试代码

#include <iostream>
#include <string>
#include "Trie.h"

int main() {   
    // 基础Trie树测试
    Trie trie;

    // 1. 插入单词
    trie.insert("apple");
    trie.insert("app");
    trie.insert("banana");
    trie.insert("band");
    trie.insert("apple"); // 重复插入

    // 2. 查询单词
    std::cout << "查询 \"apple\": " << (trie.search("apple") ? "存在" : "不存在") << std::endl;
    std::cout << "查询 \"app\": " << (trie.search("app") ? "存在" : "不存在") << std::endl;
    std::cout << "查询 \"appl\": " << (trie.search("appl") ? "存在" : "不存在") << std::endl;
    std::cout << "apple 出现次数: " << trie.getCount("apple") << std::endl;

    // 3. 查询前缀
    std::cout << "查询前缀 \"app\": " << (trie.startsWith("app") ? "存在" : "不存在") << std::endl;
    std::cout << "查询前缀 \"ban\": " << (trie.startsWith("ban") ? "存在" : "不存在") << std::endl;
    std::cout << "查询前缀 \"xyz\": " << (trie.startsWith("xyz") ? "存在" : "不存在") << std::endl;

    // 4. 打印所有单词
    std::cout << "所有单词: ";
    trie.printAllWords();

    // 5. 删除单词
    std::cout << "删除 \"app\": " << (trie.remove("app") ? "成功" : "失败") << std::endl;
    std::cout << "删除后查询 \"app\": " << (trie.search("app") ? "存在" : "不存在") << std::endl;
    std::cout << "删除后查询前缀 \"app\": " << (trie.startsWith("app") ? "存在" : "不存在") << std::endl;

    // 带权重Trie树测试
    WeightedTrie wt;
    wt.insert("apple", 10);
    wt.insert("banana", 5);
    std::cout << "\n带权重Trie测试：" << std::endl;
    std::cout << "apple 权重: " << wt.getWeight("apple") << std::endl;
    std::cout << "banana 权重: " << wt.getWeight("banana") << std::endl;
    std::cout << "orange 权重: " << wt.getWeight("orange") << std::endl;
    
    return 0;
}

输出结果

查询 "apple": 存在
查询 "app": 存在
查询 "appl": 不存在
apple 出现次数: 2
查询前缀 "app": 存在
查询前缀 "ban": 存在
查询前缀 "xyz": 不存在
所有单词: app apple banana band 
删除 "app": 成功
删除后查询 "app": 不存在
删除后查询前缀 "app": 存在

带权重Trie测试：
apple 权重: 10
banana 权重: 5
orange 权重: -1
    

六、注意事项

七、总结

Trie树是专为字符串前缀匹配设计的高效数据结构，核心是共享前缀路径和字符索引遍历。其插入/查询操作的时间复杂度仅与字符串长度相关，是哈希表、红黑树等结构无法替代的最优解。

常见坑点与避坑经验

• 字符索引计算错误：牢记 c - 'a' 仅适用于小写字母，大写字母需 c - 'A'，混合字符需统一处理；
• 忘记标记is_end：插入时未设置is_end会导致search无法识别完整单词；
• 内存泄漏：必须通过析构函数或手动删除释放节点，尤其是大规模使用场景；
• 删除逻辑错误：直接删除节点会导致共享前缀的单词丢失，需递归回溯判断节点是否可删除。

本教程通过完整的代码实现和实战示例，覆盖了Trie树的核心原理、关键操作和扩展功能。掌握Trie树的设计思想，能高效解决字符串前缀匹配、自动补全、词典检索等实际问题，是算法设计和工程开发中的重要工具。