前缀树定义的C++代码

以下是前缀树的定义的C++代码示例：

class TrieNode {
public:
    bool is_end; // 是否为字符串的结尾
    TrieNode* children[26]; // 26个小写字母

    TrieNode() {
        is_end = false;
        memset(children, NULL, sizeof(children)); // 初始化子节点为NULL
    }
};

class Trie {
public:
    TrieNode* root;

    Trie() {
        root = new TrieNode(); // 根节点不代表任何字符
    }

    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (node->children[index] == NULL) {
                node->children[index] = new TrieNode();
            }
            node = node->children[index];
        }
        node->is_end = true; // 标记字符串结尾
    }

    bool search(string word) {
        TrieNode* node = root;
        for (char c : word) {
            int index = c - 'a';
            if (node->children[index] == NULL) {
                return false;
            }
            node = node->children[index];
        }
        return node->is_end; // 判断是否为字符串结尾
    }

    bool startsWith(string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            int index = c - 'a';
            if (node->children[index] == NULL) {
                return false;
            }
            node = node->children[index];
        }
        return true; // 只要前缀存在，就返回true
    }
};

在上面的代码中，我们定义了一个`TrieNode`类表示前缀树的节点，它包含一个布尔型变量`is_end`表示该节点是否为字符串的结尾，以及一个大小为26的`children`数组，用于存储该节点的子节点。我们还定义了一个`Trie`类表示前缀树，它包含一个指向根节点的指针`root`，以及三个方法：`insert`用于插入字符串，`search`用于查找字符串，`startsWith`用于判断前缀是否存在。在插入字符串时，我们从根节点开始遍历，如果某个字符的子节点不存在，就创建一个新的子节点。在查找字符串和判断前缀是否存在时，我们也是从根节点开始遍历，如果某个字符的子节点不存在，就返回false。最后，如果遍历到字符串的结尾，我们判断该节点的`is_end`变量是否为true，以确定该字符串是否存在于前缀树中。