本文最后更新于 376 天前，其中的信息可能已经有所发展或是发生改变。
所谓Trie树，又名字典树。
如图，每个节点代表一个字母，该树的单词集合为{"cat","her,"him","no","nova"}
要Trie树中查找单词主要是查找一条路径而不是一个节点。
利用Trie树还可以进行模糊查找，例如，查找ca,可以为用户查到cat并询问。因为有相同的前缀。
c++中传统方法实现Trie树：
sturct trie_node{
int count;//代表到该节点位置，构成单词的个数
struct trie_node* next[26];//因为一共有26个字母
}
struct trie_node* new_node()
{
trie_node* newnode = new trie_node();
newnode->count = 0;
for(int i=0; i<26; i++)
newnode->children[i] = NULL;
return newnode;
}
void trie_insert(struct trie_node* root, char word[])
{
struct trie_node* node = root;//临时指针
for(int i=0;word[i]!='\0';i++)//遍历字符串
{
int index=word[i]-'a';//将a-z映射到0-26的索引
if(node->children[index] == NULL)
{
node->children[index]=create_trie_node();
}
node = node->children[index];
}
node->count += 1;
}
int search(struct trie_node* root, char word[])
{
trie_node* node = root;
for(int i=0;word[i]!='\0';i++)//遍历字符串
{
int index=word[i]-'a';//将a-z映射到0-26的索引
if(node->children[index] == NULL)
{
return 0;//该单词不存在
}
node = node->children[index];
}
return node->count;//返回该单词出现的次数
}这里把上学期课设写的那个python版本也复制过来
Python实现Trie树
class trie_node:
def __init__(self) -> None:
self.chines=""
self.child={}
self.val=False#该节点是否构成单词
class Trie:
def __init__(self) -> None:
self.root=trie_node()
self.num=0#贮存的单词数量
def insert(self,word,chines) -> None:
temp=self._search(word)
if temp!=False:
return False
tempnode=self.root
for i in word:
if i not in tempnode.child:
tempnode.child[i]=trie_node()
tempnode=tempnode.child[i]
tempnode.val=True
tempnode.chines=chines
self.num+=1
def search_word(self,word):
temp=self.search(word)
if temp==False:
#print("未查询到该单词")##这里明天得改一下，把这个写在外边，没必要写到这里，这里做测试用
return False
else:
return temp
def search(self,word):
t=''
possible=[]
tempnode=self.root
for i in word:
#print(tempnode.child.keys())
if tempnode.val==True:
possible.append("你可能在找:{}:{}".format(t,tempnode.chines))#模糊查找
if i not in tempnode.child:
return possible
tempnode=tempnode.child[i]
t+=i
#print(possible)
if tempnode.val==True:
return tempnode.chines
elif len(possible)!=0:
return possible
else:
return False
def _search(self,word):
tempnode=self.root
for i in word:
#print(tempnode.child.keys())
if i not in tempnode.child:
return False
tempnode=tempnode.child[i]
if tempnode.val==True:
return tempnode
else:
return False
def delete(self,words):
temp=self._search(words)
if temp==False:
# print("未查询到该单词")
return False
else:
self.num-=1
temp.val=False
#print("{} 已被成功删除".format(words+":"+temp.chines))aciwng例题：Trie字符串统计
维护一个字符串集合，支持两种操作：
I x向集合中插入一个字符串 x;Q x询问一个字符串在集合中出现了多少次。
共有 N个操作，所有输入的字符串总长度不超过 10^5,字符串仅包含小写英文字母。
输入格式
第一行包含整数 N，表示操作数。
接下来 N 行，每行包含一个操作指令，指令为I x或Q x中的一种。
输出格式
对于每个询问指令Q x，都要输出一个整数作为结果，表示 x在集合中出现的次数。
每个结果占一行。
数据范围
1≤N≤2∗10^4
输入样例：5 I abc Q abc Q ab I ab Q ab输出样例：
1 0 1跟着y总很大的收获是把各种数据结构用数组模拟实现了一遍，是很新的思路。
AC代码：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000000;
int a[N];
int son[N*31][2],idx;//题目a[i]的范围是0到2^31次
void insert(int x)
{
int t=0;
for(int i=30;i>=0;i--)
{
int index=x>>i&1;//取出从右往左数第i位(从0开始数)的数字。
if(!son[t][index])son[t][index]=++idx;
t=son[t][index];//指向儿子
}
}
int query(int x)
{
int ans=0;
int t=0;
for(int i=30;i>=0;i--)
{
int index=x>>i&1;
if(son[t][!index])//如果他儿子的反过来一位是存在的话，则走这一条路。
{
t=son[t][!index];
ans=(ans<<1)+!index;//相当于在末尾加上!index，
//例如:5的二进制为0101，左移之后是01010，
//加1，1的二进制为0001,加1之后为01011，加0的话亦然。
}
else
{
t=son[t][index];//反过来不存在，所以走已经存在的路
ans=(ans<<1)+index;
}
}
return ans;
}
int main()
{
int ans=0;
int n;
cin>>n;
for (int i = 0; i < n; i ++ )
{
scanf("%d", &a[i]);
insert(a[i]);
}
for (int i = 0; i < n; i ++ )
{
int t=query(a[i]);
ans=max(ans,t^a[i]);
}
cout<<ans;
return 0;
}例题2：最大异或对
在给定的 N个整数 A1，A2……AN中选出两个进行 xor（异或）运算，得到的结果最大是多少？
输入格式
第一行输入一个整数 N。第二行输入 N 个整数 A1～AN。
输出格式
输出一个整数表示答案。
数据范围
1≤N≤10^5,
0≤Ai<2^31
输入样例：
3
1 2 3输出样例：
3
两个数的异或怎么才能最大呢？
比如5： 二进制为0101，要想异或最大，必须从最高位开始，尽量和他不同，这样全取1，所以能和5异或起来最大的就是1010，也就是12。
我们将每个数的二进制从高位用Trie数存储起来，这样在找这个数的最大异或数时，从最高位开始，尽量找与他不同的，比如0101，从最高位开始遍历，第一位是1，先找第一位是0的数，如果有，那就第一位取0，如果没有我们就选1，然后往下走，以此类推，每次选与当前位不同的数，如果能选就选，如果不能选就走和他相同的。直到最后，得到最大的。
大概就这个意思
AC代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000000;
int a[N];
int son[N*31][2],idx;//题目a[i]的范围是0到2^31次
void insert(int x)
{
int t=0;
for(int i=30;i>=0;i--)
{
int index=x>>i&1;//取出从右往左数第i位(从0开始数)的数字。
if(!son[t][index])son[t][index]=++idx;
t=son[t][index];//指向儿子
}
}
int query(int x)
{
int ans=0;
int t=0;
for(int i=30;i>=0;i--)
{
int index=x>>i&1;
if(son[t][!index])//如果他儿子的反过来一位是存在的话，则走这一条路。
{
t=son[t][!index];
ans=(ans<<1)+!index;//相当于在末尾加上!index，
//例如:5的二进制为0101，左移之后是01010，
//加1，1的二进制为0001,加1之后为01011，加0的话亦然。
}
else
{
t=son[t][index];//反过来不存在，所以走已经存在的路
ans=(ans<<1)+index;
}
}
return ans;
}
int main()
{
int ans=0;
int n;
cin>>n;
for (int i = 0; i < n; i ++ )
{
scanf("%d", &a[i]);
insert(a[i]);
}
for (int i = 0; i < n; i ++ )
{
int t=query(a[i]);
ans=max(ans,t^a[i]);
}
cout<<ans;
return 0;
}