【Trie树（字典树，前缀树）】
1. 思考（字典树的应用场景）2. 什么是字典树3. 字典树的基本操作3.1 建树3.2 添加3.3 查询3.4 释放
4. 字典树的应用5. 字典树的整体代码（例：hihocoder 1014 Trie树）
1. 思考（字典树的应用场景）
一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词。对于给定字符串，查询某字典中以该字符串开头的字符串的个数。等等
遇到这些问题，如果我们每次都是一个一个的统计，遍历的话，是非常消耗时间的。但是如果你会字典树的话，你就能很快的得出答案。
那么下面我们就来学习字典树是什么样的吧。
本文后面代码主要依据第二个问题给予解答。 不同的题有不同的解答方式，但大概主题是一样的。
2. 什么是字典树
Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。 上图是一棵 Trie 树，表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
它有3个基本性质：
根节点不包含字符，除根节点外每一个节点都只包含一个字符。从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。每个节点的所有子节点包含的字符都不相同。
3. 字典树的基本操作
3.1 建树
通过结构体结构体保存当前字符，连接下个字符。 因为只有26个字母，那么我们可以创建一个结构体指针数组。用以连接后面的字符。
代码演示
struct Trie
{
int num
;
Trie
*next
[26];
};
Trie
* init()
{
Trie
* trie
=(Trie
*)malloc(sizeof(Trie
));
trie
->num
=0;
for(int i
=0;i
<26;i
++)
trie
->next
[i
]=NULL;
return trie
;
}
3.2 添加
void _insert(Trie
*root
,char *str
)
{
int len
=strlen(str
);
Trie
*p
= root
;
for(int i
=0;i
<len
;i
++)
{
int x
=str
[i
]-'a';
if(p
->next
[x
]==NULL)
p
->next
[x
] = init();
p
=p
->next
[x
];
p
->num
++;
}
}
3.3 查询
int _search(Trie
*root
,char *str
)
{
int len
=strlen(str
);
Trie
*q
= root
;
for(int i
=0;i
<len
;i
++)
{
int x
=str
[i
]-'a';
if(q
->next
[x
]==NULL)
return 0;
q
=q
->next
[x
];
}
return q
->num
;
}
3.4 释放
void _delete(Trie
*root
)
{
for(int i
=0;i
<26;i
++)
if(root
->next
[i
]!=NULL)
_delete(root
->next
[i
]);
free(root
);
}
4. 字典树的应用
字符串检索词频统计字符串排序前缀匹配作为辅助结构
5. 字典树的整体代码（例：hihocoder 1014 Trie树）
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std
;
struct Trie
{
int num
;
Trie
*next
[26];
};
Trie
* init()
{
Trie
* trie
=(Trie
*)malloc(sizeof(Trie
));
trie
->num
=0;
for(int i
=0;i
<26;i
++)
trie
->next
[i
]=NULL;
return trie
;
}
void _insert(Trie
*root
,char *str
)
{
int len
=strlen(str
);
Trie
*p
= root
;
for(int i
=0;i
<len
;i
++)
{
int x
=str
[i
]-'a';
if(p
->next
[x
]==NULL)
p
->next
[x
] = init();
p
=p
->next
[x
];
p
->num
++;
}
}
int _search(Trie
*root
,char *str
)
{
int len
=strlen(str
);
Trie
*p
= root
;
for(int i
=0;i
<len
;i
++)
{
int x
=str
[i
]-'a';
if(p
->next
[x
]==NULL)
return 0;
p
=p
->next
[x
];
}
return p
->num
;
}
int main()
{
int n
,t
;
char str
[45];
scanf("%d",&n
);
Trie
*root
= init();
while(n
--)
{
scanf("%s",str
);
_insert(root
,str
);
}
scanf("%d",&t
);
while(t
--)
{
scanf("%s",str
);
cout
<< _search(root
,str
) << endl
;
}
return 0;
}
