前缀树介绍
数风流人物，还看今朝！
前缀树
Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。
前缀树，也叫做字典树（Trie），是一种专门处理字符串数据的数据结构。它特别适合用来处理和查询大量的字符串，比如词汇表、域名等。
想象一下，你有一大堆单词，你想快速地查找某个单词是否存在，或者找到以某个前缀开始的所有单词。用普通的列表或者哈希表来做这些操作可能不太高效，尤其是当数据量很大时。这时，前缀树就能派上用场了。
前缀树的基本思想是利用字符串的公共前缀来减少查询的时间。它就像一棵倒立的树，每个节点代表一个字符。从根节点开始，每条边代表一个字符，通向下一个节点。这样，整个路径就组成了一个字符串。
举个简单的例子，假设有以下几个单词：cat, car, dog, dart，dac
这样，每个单词都有一条从根节点到叶节点的路径，路径上的字符连起来就是这个单词。
前缀树的厉害之处在于，它可以非常快速地查找以某个前缀开始的单词。比如，如果你想找出所有以 ‘ca’ 开头的单词，你只需要从根节点沿着 ‘c’ 和 ‘a’ 的边走下去，然后收集所有从那个节点出发的路径，就能得到 ‘cat’ 和 ‘car’。
此外，前缀树还可以用来检查一个单词是否已经存在。你只需要沿着单词的每个字符走路径，看是否能到达一个表示单词结束的节点。
请你实现 Trie 类：
-
Trie()初始化前缀树对象。 -
void insert(String word)向前缀树中插入字符串word。 -
boolean search(String word)如果字符串word在前缀树中，返回true（即，在检索之前已经插入）；否则，返回false。 -
boolean startsWith(String prefix)如果之前已经插入的字符串word的前缀之一为prefix，返回true；否则，返回false
struct Node {
vector<Node*>son;
bool end ; // 创建一个bool值的end，代表是否是终止节点
Node():son(26,NULL),end(false){}
};
class Trie {
Node* root = new Node(); // 创建一个根节点
// 返回三种数字，0，1，2
// 0代表没有这个单词
// 1代表有这个单词，但不是结尾
// 2代表有这个单词，且是结尾
int find(string word) {
auto cur = root; // 遍历字符串 word，同时用一个变量 cur 表示当前在 26
// 叉树的哪个节点，初始值为 root。
for (auto c : word) {
c -= 'a';
if (cur->son[c] == nullptr) {
return 0;
} // 如果 word[i] 不是 cur 的儿子，返回 0。search 和
// startsWith 收到 0 之后返回 false。
cur = cur->son[c]; // 更新 cur 为儿子列表中的相应节点。
}
// 如果cur->end为true，说明有这个单词，且是结尾
// 如果cur->end为false，说明有这个单词，但并不是结尾，中间就结束了
return cur->end ? 2 : 1;
}
public:
void insert(string word) {
auto cur =root; // 变量 cur 表示当前在 26 叉树的哪个节点，初始值为 root。
for (auto c : word) {
c -= 'a';
// 如果之前没有就新建一个节点
if (cur->son[c] == nullptr) {
cur->son[c] = new Node();
}
cur = cur->son[c]; // 更新 cur 为儿子列表中的相应节点。
}
cur->end = true; // 把end置为空
}
// search:如果字符串word已经在前缀树当中，返回true
bool search(string word) {
return find(word) == 2;
}
// startwith：如果前缀prefix已经在前缀树当中，返回true
bool startsWith(string prefix) {
// 是1，2都行,0不行
return find(prefix) != 0;
}
};
很遗憾，在力扣里面是付费的，牛客里面不付费。
这个是1804.实现前缀树II，这里和上面的不同在于，一个是判断word单词是否出现，一个是查询前缀树里，word单词出现了几次，一个是查询前缀树里，是否有单词以pre做前缀，一个是一个是查询前缀树里，有多少单词以pre做前缀
此时的节点是维护pass,end,和nexts数组，如果有节点经过，pass++，一个单词结束end++，维护这两个信息。
// 测试链接 : https://leetcode.cn/problems/implement-trie-ii-prefix-tree/
public class Code01_TrieTree {
// 路是数组实现的
class Trie{
class TrieNode {
public int pass;
public int end;//单词的结尾
public TrieNode[] nexts;
public TrieNode() {
pass = 0;
end = 0;
nexts = new TrieNode[26];
}
}
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode node = root;
node.pass++;
for (int i = 0, path; i < word.length(); i++) { // 从左往右遍历字符
path = word.charAt(i) - 'a'; // 由字符，对应成走向哪条路
if (node.nexts[path] == null) {
node.nexts[path] = new TrieNode();
}
node = node.nexts[path];
node.pass++;
}
node.end++;
}
// 如果之前word插入过前缀树，那么此时删掉一次
// 如果之前word没有插入过前缀树，那么什么也不做
public void erase(String word) {
if (countWordsEqualTo(word) > 0) {
TrieNode node = root;
node.pass--;
for (int i = 0, path; i < word.length(); i++) {
path = word.charAt(i) - 'a';
if (--node.nexts[path].pass == 0) {
node.nexts[path] = null;
return;
}
node = node.nexts[path];
}
node.end--;
}
}
// 查询前缀树里，word单词出现了几次
public int countWordsEqualTo(String word) {
TrieNode node = root;
for (int i = 0, path; i < word.length(); i++) {
path = word.charAt(i) - 'a';
if (node.nexts[path] == null) {
return 0;
}
node = node.nexts[path];
}
return node.end;
}
// 查询前缀树里，有多少单词以pre做前缀
public int countWordsStartingWith(String pre) {
TrieNode node = root;
for (int i = 0, path; i < pre.length(); i++) {
path = pre.charAt(i) - 'a';
if (node.nexts[path] == null) {
return 0;
}
node = node.nexts[path];
}
return node.pass;
}
}
原文地址：https://blog.csdn.net/m0_75266675/article/details/144755733
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！