本文共 2772 字，大约阅读时间需要 9 分钟。

前缀树（Trie）是一种非常有用的数据结构，用于高效地存储和检索字符串。以下是关于前缀树的两版实现的详细说明。

第一版代码：使用数组和链表结构

第一版代码使用数组和链表结构来实现前缀树。每个节点包含一个path和一个end字段，以及一个指向下一个节点的next指针。path字段用于记录当前节点的路径长度，用于判断是否存在以当前字符开头的字符串。end字段用于记录当前节点是否是某个完整单词的终点。

结构定义

struct Node {    int path = 0; // 可以判断是否存在这个前缀    int end = 0; // 可以判断出现的次数    Node* next = nullptr;    vector
   
     v_node;    Node() {        v_node.resize(26, nullptr);    }};
   

实现类

class Trie {    Node* root;public:    Trie() {        root = new Node();    }    void insert(string word) {        Node* tmp = root;        for (int i = 0; i < word.size(); ++i) {            int index = word[i] - 'a';            if (tmp->v_node[index] == nullptr) {                tmp->v_node[index] = new Node();            }            tmp = tmp->v_node[index];            ++tmp->path;        }        ++tmp->end;    }    bool search(string word) {        Node* tmp = root;        for (int i = 0; i < word.size(); ++i) {            int index = word[i] - 'a';            if (tmp->v_node[index] == nullptr) {                return false;            }            tmp = tmp->v_node[index];        }        return tmp->end >= 1 ? true : false;    }    bool startsWith(string prefix) {        Node* tmp = root;        for (int i = 0; i < prefix.size(); ++i) {            int index = prefix[i] - 'a';            if (tmp->v_node[index] == nullptr) {                return false;            }            tmp = tmp->v_node[index];        }        return true;    }};

第二版代码：使用哈希表和更灵活的结构

第二版代码改用哈希表来存储节点，避免了固定数组的长度限制。哈希表（如unordered_map）提供了更大的灵活性，特别适用于单词数量不确定的情况。

结构定义

struct Node {    int path = 0;    int end = 0;    unordered_map
   
     u_Node;};
   

实现类

class Trie {    Node* root;public:    Trie() {        root = new Node();    }    void insert(string word) {        Node* tmp = root;        for (int i = 0; i < word.size(); ++i) {            char c = word[i];            if (tmp->u_Node.find(c) == tmp->u_Node.end()) {                tmp->u_Node[c] = new Node();            }            tmp = tmp->u_Node[c];            ++tmp->path;        }        ++tmp->end;    }    bool search(string word) {        Node* tmp = root;        for (int i = 0; i < word.size(); ++i) {            char c = word[i];            if (tmp->u_Node.find(c) == tmp->u_Node.end()) {                return false;            }            tmp = tmp->u_Node[c];        }        return tmp->end >= 1;    }    bool startsWith(string prefix) {        Node* tmp = root;        for (const auto& c : prefix) {            if (tmp->u_Node.find(c) == tmp->u_Node.end()) {                return false;            }            tmp = tmp->u_Node[c];        }        return true;    }};

总结

这两版代码展示了前缀树的两种不同实现方式：第一版使用数组和链表结构，第二版改用哈希表，提供了更大的灵活性。无论是哪种实现，前缀树都在文本处理、搜索引擎、自动完成功等领域中发挥着重要作用。通过这些实现，我对前缀树的工作原理有了更深入的理解，也为未来的算法学习打下了坚实的基础。