一本通-1337：【例3-2】单词查找树

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

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

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

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

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

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

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

【输入样例】 A AN ASP AS ASC ASCII BAS BASIC

【输出样例】 13

---

统计字典树的节点个数，其实就是个N叉树的层序遍历就解决了。知识另外注意，root节点也要算进去。

#include <bits/stdc++.h>

using namespace std;

class Trie
{
    struct TrieNode
    {
        TrieNode *child[26];
        TrieNode() {
            for (int i = 0; i < 26; ++i) child[i] = NULL;
        }
    };
    TrieNode *root;


public:
    Trie() { root = new TrieNode(); }
    ~Trie() { makeEmpty(root); }

    void makeEmpty(TrieNode *&root)
    {
        if (root) {
            for (int i = 0; i < 26; ++i) {
                makeEmpty(root -> child[i]);
            }
            delete root;
            root = NULL;
        }
    }

    void insert(string & s)
    {
        TrieNode *p = root;
        int n = s.size();
        for (int i = 0; i < n; ++i) {
            int id = s[i] - 'A';
            if (!p -> child[id]) p -> child[id] = new TrieNode();
            p = p -> child[id];
        }
    }

    int calculate()
    {
        int cnt = 0;
        queue<TrieNode *> q;
        for (int i = 0; i < 26; ++i) {
            if (root -> child[i]) q.push(root -> child[i]);
        }

        while (!q.empty()) {
            TrieNode *tmp = q.front(); q.pop();
            ++cnt;
            for (int i = 0; i < 26; ++i) {
                if (tmp -> child[i]) q.push(tmp -> child[i]);
            }
        }

        return cnt + 1; //root节点也算进去
    }

};


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Trie trie;
    string s;
    while (cin >> s) {
        trie.insert(s);
    }
    cout << trie.calculate() << endl;

    return 0;
}