字典树

【数据结构】字典树TrieTree图文详解-CSDN博客

字典树，英文名 trie。顾名思义，就是一个像字典一样的树。

trie1

可以发现，这棵字典树用边来代表字母，而从根结点到树上某一结点的路径就代表了一个字符串。

前缀树的3个基本性质：

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

查的话就正常查，不过必须记住要是在叶子节点，不然也不算在

代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
const int N = 1000050;
int trie[N][26];
//N是树的层数
int cnt[N];
//看是不是以这个字母结尾，以及如果以这个字母结尾，究竟是结尾了多少次呢
int id;
//节点的编号
void insert(string s)
    //插入函数
    //需要一个字符串
{
	int p = 0;
    //插入自然也是从根节点开始，注意，根节点不存储字符
	for (int i = 0; i < s.size(); i++)
        //遍历字符串
	{
		int x = s[i] - 'a';
        //进行字母的一个小变形，因为我们得到0-25
		if (trie[p][x] == 0) trie[p][x] = ++id;
        //如果没有所对应的字母没有，就建一个
		p = trie[p][x];
        //然后接下来p就是这个刚建立的字母哩
	}
	cnt[p]++;
    //遍历完了，出循环，也就是说字母存储结束了，但我们需要知道，于是cnt用来记录结束否
}
//插入就讲完了，感觉还是很清晰的
int  find(string s)
{
	int p = 0;
    //查找一样从根节点开始查找
	for (int i = 0; i < s.size(); i++)
	{
        //遍历字符串
		int x = s[i] - 'a';
        //依然变形
		if (trie[p][x] == 0)return 0;
        //如果没有，就返回
		p = trie[p][x];
        //有的话就好了，就继续往下搜
	}
	return cnt[p];
    //遍历完了，康康是不是结束的那个节点，妙哉啊
}

trie[i] [x]=0,代表字典树中目前没有这个点

trie[i] [x]的值代表这个点下方连有的点的编号

例如：trie[i] [2]=9代表第i号点和的下方连有一个点‘c’，并且那个点的编号是9

cnt[N]: cnt[i]==0代表编号为i的点不是一个单词的结束点

cnt[i]!=0代表编号为i的点是一个单词的结束点。

cnt[i]不一定只为0或1，因为有可能多次输入了同一个单词。

trie[p] [x] 查找连着目标字母的节点的编号，如果目标节点存在，就把p更新成目标节点的编号（p = trie[p] [x]）。

如果trie[p] [x] == 0，代表字典树中没有这个点，如果是查找就代表没有这个单词，查找失败。

而如果是插入函数，我们就用 ++id 来把这个点存进字典树。

我们在两个函数的最后用cnt[p]来涂红节点或返回节点值。