Trie树—高级树型结构_组织树结构高级

Trie树基本概念

Trie 树中文名叫字典树、前缀树等等。这些名字暗示其与字符的处理有关，事实也确实如此，它主要用途就是将字符串（当然也可以不限于字符串）整合成树形。

它的核心思想就是通过最大限度地减少无谓的字符串比较，使得查询高效率，即「用空间换时间」，再利用共同前缀来提高查询效率。

典型应用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

Trie树特点

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

假设有5个字符串，它们分别是：Code，Cod，Cook，Five，File，Fat。按照Trie树的组织结构如下图：

Trie树数据结构

class Trie_node
{
   
public:
	Trie_node(char word = 0)
	{
   
		this->word = word;
		exist = false;
		count = 1; // 每个字符初始化就算一个前缀了
		memset(next, 0, sizeof(next)
1
2
3
4
5
6
7
8
9
10