C++类实现Trie树问题：设置isEndOfWord后搜索无法正确判断

我来帮你排查这个核心问题！你的search方法大概率是在遍历完单词所有字符后直接返回了true，没去验证当前节点的isEndOfWord标记——这可是Trie区分「完整单词」和「前缀」的关键（比如"app"和"apple"，前者是后者的前缀，但只有插入过的单词才应该被搜索命中）。

先看常见的错误Search写法（反面示例） #

这种写法会把未插入的前缀误判为存在：

bool search(string word) {
    TrieNode* current = root;
    for (char c : word) {
        int index = c - 'a';
        if (!current->children[index]) {
            return false;
        }
        current = current->children[index];
    }
    // 错误：直接返回true，忽略了isEndOfWord的验证
    return true;
}

正确的实现方案 #

1. 完善TrieNode类（确保getter/setter逻辑正确） #

class TrieNode {
private:
    TrieNode* children[26];
    bool isEndOfWord;
public:
    TrieNode() {
        // 初始化所有子节点为空指针
        for (int i = 0; i < 26; ++i) {
            children[i] = nullptr;
        }
        isEndOfWord = false; // 默认不是单词结尾
    }

    // Getter方法
    bool getIsEndOfWord() const {
        return isEndOfWord;
    }
    TrieNode* getChild(int index) const {
        if (index < 0 || index >= 26) return nullptr;
        return children[index];
    }

    // Setter方法
    void setIsEndOfWord(bool value) {
        isEndOfWord = value;
    }
    void setChild(int index, TrieNode* node) {
        if (index >= 0 && index < 26) {
            children[index] = node;
        }
    }
};

2. 正确的Insert和Search方法实现 #

class Trie {
private:
    TrieNode* root;
public:
    Trie() {
        root = new TrieNode();
    }

    void insert(string word) {
        TrieNode* current = root;
        for (char c : word) {
            int index = c - 'a';
            if (!current->getChild(index)) {
                // 子节点不存在则创建新节点
                current->setChild(index, new TrieNode());
            }
            current = current->getChild(index);
        }
        // 遍历完单词后，标记当前节点为单词结尾
        current->setIsEndOfWord(true);
    }

    bool search(string word) {
        TrieNode* current = root;
        for (char c : word) {
            int index = c - 'a';
            if (!current->getChild(index)) {
                // 字符不存在，直接返回false
                return false;
            }
            current = current->getChild(index);
        }
        // 核心：遍历完所有字符后，必须检查当前节点是否是单词结尾
        return current->getIsEndOfWord();
    }
};

测试验证代码 #

你可以用这段代码验证逻辑是否正确：

#include <iostream>
#include <string>
using namespace std;

// 上面的TrieNode和Trie类代码放在这里

int main() {
    Trie trie;
    trie.insert("apple");
    cout << boolalpha << trie.search("apple") << endl; // 输出true
    cout << boolalpha << trie.search("app") << endl;   // 输出false（仅前缀未插入）
    trie.insert("app");
    cout << boolalpha << trie.search("app") << endl;   // 输出true（已插入完整单词）
    return 0;
}

额外排查点 #

如果按上述写法仍有问题，检查这几点：

• 确认insert方法确实在单词的最后一个字符节点上调用了setIsEndOfWord(true)，没有遗漏
• 检查getIsEndOfWord方法是否正确返回成员变量，有没有写错变量名
• 确保TrieNode构造函数正确初始化isEndOfWord为false，避免默认值混乱

内容的提问来源于stack exchange，提问作者susil95