NOI2000 單詞查找樹 解題報告

            【NOI2000】单词查找树 

Description

在进行文法分析的时候，通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度，通常都要画出与单词列表所对应的单词查找树，其特点如下：
1)根节点不包含字母，除根节点外每一个节点都仅包含一个大写英文字母；
2)从根节点到某一节点，路径上经过的字母依次连起来所构成的字母序列，称为该节点对应的单词。单词列表中的每个词，都是该单词查找树某个节点所对应的单词；
3)在满足上述条件下，该单词查找树的节点数最少。

Input

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

Output

输出仅包含一个整数和一个换行/回车符。该整数为单词列表对应的单词查找树的节点数。

Sample Input

A
AN
ASP
AS
ASC
ASCII
BAS
BASIC

Sample Output

13

【閒扯】
話說NOI2000的題目真是水，第一題是【瓷片項鍊】，就是一個一元二次函數的最值問題，第二題是這個題，真是簡單啊！

 【分析】
單詞查找樹就是字典樹（Trie Tree），可以參看我以前的文章。先用字典樹把所有的字符串均插入字典樹，然後再遍歷(Travel)整個樹，先序、中序、後序，怎麼遍歷都可以，可以寫遞歸函數來壓縮代碼複雜度。

【滿分代碼】
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

const int sonnum=26;
const char base='A';
class Trie
{
public:
    bool isStr;
    int Page;
    class Trie *son[sonnum];
};

Trie *NewTrie()
{
    Trie *temp=new Trie;
    temp->isStr=false;
    for (int i=0;i<sonnum;i++)
        temp->son[i]=NULL;
    return temp;
}

void Insert(Trie *pnt,char *s,unsigned int len)
{
    Trie *temp=pnt;
    for (unsigned int i=0;i<len;i++)
    {
        if (temp->son[s[i]-base]==NULL)
            temp->son[s[i]-base]=NewTrie();
        temp=temp->son[s[i]-base];
    }
    temp->isStr=true;
}

Trie *pnt=NewTrie();
int T=0;

void Digui(Trie *temp)
{
    T++;
    for (int i=0;i<sonnum;i++)
    {   
        if(temp->son[i]!=NULL)
            Digui(temp->son[i]);
    }
}

void init()
{
    char str[65];
    while (cin>>str)
        Insert(pnt,str,strlen(str));
    Digui(pnt);
}

int main()
{
   
    freopen("trie.in","r",stdin);
    freopen("trie.out","w",stdout);
    init();
    cout<<T<<endl;
    fclose(stdin);
    fclose(stdout);
    return 0;
}