信息学奥赛一本通 1337：【例3-2】单词查找树 | 洛谷 P5755 [NOI2000] 单词查找树

【题目链接】

ybt 1337：【例3-2】单词查找树
洛谷 P5755 [NOI2000] 单词查找树

【题目考点】

1. 字典树

【解题思路】

解法1：字典树

字典树模板题。学习字典树相关知识请在csdn搜“字典树”或“tire树”。
该题说文件总长度不超过32K，$32KB=32\ast 1024B=32768B$，总字符个数不会超过33000个。因此结点池总数量设为33000。

【题解代码】

解法1：字典树

#include<bits/stdc++.h>
using namespace std;
struct Node
{
    
    int child[26];//child[i]:字符是i+'A'的孩子结点的地址 
};
Node node[33000];
int p, root;//根结点root地址为0，从地址1开始分配结点 
void insert(string s)//向字典树插入单词s 
{
    
    int pf = root;//当前关注的结点的地址 
    for(int i = 0; i < s.length(); ++i)
    {
    
        if(node[pf].child[s[i]-'A'] == 0)
            node[pf].child[s[i]-'A'] = ++p;//分配新结点 
        pf = node[pf].child[s[i]-'A'];//pf指向下一个结点 
    }
}
int getNodeNum(int r)//获取根结点地址为r的树的结点数 
{
    
    int sum = 1;//自己就是1个结点 
    for(int i = 0; i < 26; ++i)//统计r子树结点数量 
    {
    
        if(node[r].child[i] > 0)
            sum += getNodeNum(node[r].child[i]);
    }
    return sum;
}
int main()
{
    
    string s;
    while(cin >> s)
        insert(s);//将单词s插入字典树 
    cout << getNodeNum(root);//获取整棵树的结点数 
    return 0;
}