当前位置：首页 > news >正文

【例3-2】单词查找树（信息学奥赛一本通- P1337）

news 2026/8/16 16:51:04

【题目描述】

在进行文法分析的时候，通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度，通常都画出与单词列表所对应的单词查找树，其特点如下：

1．根结点不包含字母，除根结点外每一个结点都仅包含一个大写英文字母；

2．从根结点到某一结点，路径上经过的字母依次连起来所构成的字母序列，称为该结点对应的单词。单词列表中的每个单词，都是该单词查找树某个结点所对应的单词；

3．在满足上述条件下，该单词查找树的结点数最少。

4．例如图3-2左边的单词列表就对应于右边的单词查找树。注意，对一个确定的单词列表，请统计对应的单词查找树的结点数（包含根结点）。

【输入】

为一个单词列表，每一行仅包含一个单词和一个换行/回车符。每个单词仅由大写的英文字母组成，长度不超过63个字母。文件总长度不超过32K，至少有一行数据。

【输出】

仅包含一个整数，该整数为单词列表对应的单词查找树的结点数。

【输入样例】

A AN ASP AS ASC ASCII BAS BASIC

【输出样例】

1. 关于那个“文件总长度 32K”

题目给的限制很有意思：

单词长度不超过 63。
文件总长度不超过 32K。

第一眼看到 63，下意识觉得“这题很小”，随手开了个 tre[2000]。结果仔细一算不对劲：

32K 是多少？

在C++里，一个char就是 1 字节。

32K=32*1024=32768字节。

这意味着最坏情况下（比如所有单词都长得不一样），这棵树得存 3 万多个字符。

如果要建树，数组至少得开到 40000+ 才稳。

要是按 2000 开，读到第 2001 个字符的时候程序直接就炸了（越界）。

教训：以后看到 32K、64M 这种单位，第一反应必须是换算成字节数。

2. 为什么用 vector 存 Trie？

通常 Trie 树节点是这样写的：

struct node { char data; node* next[26]; // 或者 int next[26] };

这样写查找快，但如果节点很多且分叉少，空间浪费严重。

改用vector邻接表写法：

struct node { char data; vector<int> son; // 只存存在的儿子下标 } tre[50000]; // 数组一定要开够！

虽然查找时要遍历son数组（多一个 for 循环），但省内存，而且代码写起来其实就是个 DFS，很符合直觉。

3. 最终代码

逻辑很简单：

拿着字符串当前字符a[k2]去当前节点k1的son列表里找。
找到了 -> 递归下一层。
找不到 ->push_back一个新节点，把ind传进去继续递归。

#include <bits/stdc++.h> #include <vector> using namespace std; struct node{ char data;//记录该结点是哪个字母 vector<int> son;//存放该结点的儿子在树中的下标 }tre[50000];//要开大一点，题目中说文件总长度不超过32K，32k=三万多字节，所以开五万 int cnt;//节点个数 string a; //让tre[1]存放root int len; int ind=1;//现在已经添加了ind个节点，初始为1，因为根节点为root，不包含任何字母 void dfs(int k1,int k2){//现在遍历到树第k1个节点，字符串遍历到第k2个位置 if(k2==len) return; bool flag=0; for(int i=0;i<tre[k1].son.size();i++){//遍历该节点所有孩子，如果和字符串该位置的字母有对应，就去找下一个对应 if(tre[tre[k1].son[i]].data==a[k2]){//如果对应上了，就进入下一轮遍历 dfs(tre[k1].son[i],k2+1); flag=1; break;//对应上了就不需要再找了，退出此轮循环 } } if(flag==0){//目前没有能匹配上的 tre[++ind].data=a[k2];//把a[k2]创建一个新节点，然后储存起来 tre[k1].son.push_back(ind);//把a[k2]节点存进父节点的孩子里，就是拼接上去 dfs(ind,k2+1); } } int main(){ while(cin>>a){ len=a.size();//字符串长度 //建树 //长度不超过63个字母 即每次读进来的单词最多63个字符 dfs深度最多63层 dfs(1,0);//从树的第1个节点开始遍历，从a字符串的a[0]开始遍历 } cout<<ind; }