CSP-S 提高级 · CSP 2025 提高级第一轮 第 4 题

将字符串 $\tt cat$, $\tt car$, $\tt cart$, $\tt case$, $\tt dog$, $\tt do$ 插入一个空的 Trie 树（前缀树）中。构建完成 Trie 树（包括根节点）共有多少个结点？

这题本质就是数 Trie 里有多少个‘字符节点’，再别忘了加根节点。插入时只要遇到没走过的分支就新建节点，已走过的直接复用，逐个串插入后把节点数累加即可。

最容易丢根节点，把总数少算 1；其次是在 case 和 cart 那里，看到都有 c-a 就以为可以合并，其实 case 走 s 而 cart 走 r，分叉后各自独立；还有 dog 和 do，do 是 dog 的前缀，所以 do 不新增节点，有人会多算一个。

这道题考查字典树（Trie）的构造与节点计数。Trie 的核心思想是：根节点为空，每个子节点代表一个字符，相同前缀的字符串共享路径，只有新出现的字符才会新建节点。因此，插入一串单词后，节点总数 = 所有单词中‘真正被创建’的字符节点数 + 1（根节点）。命题人喜欢在这里挖坑：一是漏算根节点，二是误以为某个字符在不同路径上还能复用，三是没注意到前缀关系导致多算节点。拿到题先想：把每个单词按字母拆开，从根往下走，遇到没走过的字符就新建，走过的直接通过，最后数一下新建了多少个字符节点，再加 1 就是答案。

现在逐个插入题目给出的单词： 1. 插入 cat：根 → c → a → t，新建 3 个节点，当前共 4 个。 2. 插入 car：已有 c → a，只需新建 r，+1 个节点，共 5 个。 3. 插入 cart：已有 c → a → r，只需新建 t，+1 个节点，共 6 个。 4. 插入 case：已有 c → a，但接下来是 s，而 cart 走的是 r，所以必须新建 s → e，+2 个节点，共 8 个。 5. 插入 dog：全新分支 d → o → g，+3 个节点，共 11 个。 6. 插入 do：已有 d → o，无需新建，+0 个节点，共 11 个。

树的结构清晰可见：根节点下分出 c 和 d 两条主线；c 线再分 a，a 线又分 r 和 s，r 线挂 t（cart 结尾），s 线挂 e（case 结尾）；d 线挂 o（do 结尾），o 线再挂 g（dog 结尾）。所有字符节点加起来正好 10 个，加上根节点就是 11 个。

避坑提醒：根节点必须计入，这是很多学生习惯性忽略的点；case 和 cart 在 a 之后立刻分叉，不能因为都有 c-a 就认为后续能共享；do 是 dog 的前缀，所以 do 不产生新节点。记住 Trie 的计数公式：节点数 = 所有单词中‘未被共享’的字符总数 + 1。

从考频数据看，字典树在题库中只出现过 1 次，且集中在 2025 年的 CSP 提高级，说明这是一个低频但高区分度的考点，命题人往往用它来考察对前缀共享机制的直观理解。未来这类题目大概率会继续以‘构造后数节点’或‘判断某路径是否存在’的形式出现，难度不会突然拔高，但会注重细节陷阱。暂无足够依据预测更具体的变体形式。