字典树-单词查找树，Trie树

1、

哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

根节点不包含字符，除根节点外每一个节点都只包含一个字符； 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串； 每个节点的所有子节点包含的字符都不相同。

 

如果将指针变量指向一个已开辟过的，即已有的空间，就不需要重新开辟内存空间了，只有需要开辟的时候才开辟内存空间

https://blog.csdn.net/faihung/article/details/90648217    int *q;只有地址，没有内存空间。这个地址是随机地址。

像下面这种分配好的就不用new

 ///////////////////////////////int *p 只能指向别人的内存不能在栈上自动分配了（*p=1是错的）

 

class Solution {
public:
    class Tree{
    public:
        bool word_here=false;
        Tree* v[26]={nullptr};
        static void insert(Tree* t, const string &s){
            for(char c:s){
                if(!t->v[c-'a'])//t->v[c - 'a'] == nullptr
                    t->v[c-'a'] = new Tree();//一开始都是空的都要分配空间
                t = t->v[c-'a'];
            }
            t->word_here = true;
        }
        static bool search(Tree* t, const string &s){
            for(char c:s){
                if(!t->v[c-'a']->word_here)//查找c失败 false  这里判断之前的前缀是不是单独的一个字符串
                    return false;
                t = t->v[c-'a'];
            }
            return true;
        }
    };
    string longestWord(vector<string>& words) {
        Tree* root = new Tree();
        for(string &s:words)
            Tree::insert(root, s);//插入
        string longest;
        for(string &s:words)
            if(Tree::search(root, s)){
                if(s.size()>longest.size())
                    longest=s;
                else if(s.size()==longest.size()&&s<longest)////这里最后比较大小
                    longest=s;
            }
        return longest;
    }
};

 

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////参考/////////////////////////////////////////////////////////

#include<cstdio>
#include<cstdlib>
using namespace std;
char s[11];
struct Trie{
    Trie* next[26];          //结构体指针 有26种字符
    int sum;                //单词出现的次数
    Trie(){                    //构造函数 便于初始化
        for(int i=0;i<26;i++){             //初始化
            next[i]=NULL;        //初始时，每个字符所对应数组下标中的指针为空
        }
        sum=0;
    }
}root;
void insert(char* s)   //创建字典树 在字典树上插入结点
{
    Trie* p=&root;            //从根结点开始遍历
    for(int i=0;s[i];i++){         //遍历单词的每一个字符
        if(p->next[s[i]-'a']==NULL){   //判断字符所对应结构体指针数组下标中的指针是否为空
            p->next[s[i]-'a']=new Trie;  //如果为空 就新建一个结点 
        }
        p=p->next[s[i]-'a'];   //将指针指向当前字符所对应的结构体指针数组的下标所对应的地址
        p->sum++;
    }
}
int find(char* s)        //查找单词
{
    Trie* p=&root;       //从根结点开始遍历
    for(int i=0;s[i];i++){      //遍历单词的每一个字符
        if(p->next[s[i]-'a']==NULL)return 0;   // 如果下标所对应的指针为空 查找失败
        else p=p->next[s[i]-'a'];   //如果不为空 遍历下一个字符 直至遍历结束
    }
    return p->sum;   //返回遍历完的最后一个结点中所对应的数据 代表当前当前单词出现的次数
}
int main(){
    while(gets(s)&&s[0]!='\0')             //读取字典中的单词 将其插入字典树中
        insert(s);
    while(scanf("%s",s)==1){           //在字典树中查找单词出现的次数
        printf("%d\n",find(s));
    }
    return 0;
}