字典树（Trie）字符串存在性判定及节点特性技术问询

Hey there! Let's break down these common Trie questions one by one—they're super fundamental but easy to mix up when you're first learning the data structure.

1. 如何判断一个字符串是否存在于字典树（Trie）中？ #

判断逻辑很直观，分两步走：

• 从字典树的根节点开始，逐个遍历目标字符串的每个字符。
• 对每个字符，计算它在子节点数组中的索引（比如小写字母就是 c - 'a'），如果当前节点的对应子节点是 nullptr，直接返回 false——说明这个字符串的前缀都不存在，更别说完整字符串了。
• 如果顺利遍历完所有字符，关键一步：检查当前节点是否被标记为「单词终点」。因为你可能只是找到了一个前缀（比如树里有"paper"，你查"pap"能走完字符，但它不是一个完整单词）。

举个简单的伪代码例子（C++风格）：

bool search(string word) {
    TrieNode* curr = root;
    for (char c : word) {
        int idx = c - 'a';
        if (!curr->children[idx]) {
            return false;
        }
        curr = curr->children[idx];
    }
    // 必须检查是否是单词终点，而非仅走到最后一个字符
    return curr->is_end;
}

2. 关于单词终点节点的标识问题 #

你说的这种描述不一致很正常——本质上都是为了区分「前缀」和「完整单词」，只是实现方式不同而已：

• 大部分资料用布尔值（比如is_end），也有用特殊标识（比如存储单词本身、或计数器记录多少单词以该节点结尾），核心逻辑都是标记这个节点是某个完整单词的结束位置。

针对你的例子：

• 查询"pap"时，虽然能顺利遍历到对应的节点，但如果这个节点的is_end是false，就说明它只是"paper"的前缀，不是可识别的单词。
• 要把"pap"设为可识别的单词，只需要在插入"pap"时，遍历完最后一个字符'p'后，把当前节点的is_end设为true就行。比如插入的伪代码：

void insert(string word) {
    TrieNode* curr = root;
    for (char c : word) {
        int idx = c - 'a';
        if (!curr->children[idx]) {
            curr->children[idx] = new TrieNode();
        }
        curr = curr->children[idx];
    }
    // 标记该节点为单词终点
    curr->is_end = true;
}

3. 分支末尾的节点，子节点数组是否全为nullptr？ #

答案是不一定，这里要先区分两个概念：「单词的终点节点」和「字典树的分支末尾节点」：

• 「单词的终点节点」只是说这个节点对应某个完整单词的结尾，但它可能还有子节点（比如你插入了"pap"和"paper"，那么"pap"的节点是单词终点，但它的子节点里还有对应'e'的节点）。
• 只有当某个节点是整个字典树的最末端——没有任何子节点的时候，它的子节点数组才会每个索引都是nullptr。

举个例子：如果字典树里只有"pap"这一个单词，那么"pap"对应的节点的子节点数组全是nullptr；但如果同时有"pap"和"paper"，那"pap"的节点的子节点数组中，对应'e'的位置是有节点的，其他索引可能是nullptr，但不是全部。

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