前缀树定义
时间: 2023-07-01 14:19:02 浏览: 62
前缀树(Prefix Tree),也叫字典树(Trie Tree),是一种树形数据结构,用于高效地存储和搜索字符串集合。它的每个节点代表一个字符串的前缀,从根节点到叶子节点的路径表示一个完整的字符串。前缀树是一棵多叉树,每个节点有若干个子节点,每个子节点对应一个字符,而路径上的字符组成的字符串即为该节点代表的字符串。前缀树的根节点不代表任何字符,它的所有子节点代表集合中出现的所有字符。
举个例子,假设我们要存储字符串集合{"cat", "car", "dog", "do"}。那么前缀树的结构如下:
```
root
/ \
c d
/ \ \
a r o
/ / \
t g o
```
其中,根节点不表示任何字符,它的子节点c和d分别代表字符c和d。节点c的子节点a和r分别代表字符串"ca"和"cr"的前缀。节点a的子节点t代表字符串"cat",节点r的子节点代表字符串"car"。节点d的子节点o代表字符串"do"和"dog"的前缀,节点o的子节点g代表字符串"dog"。
相关问题
前缀树定义的C++代码
以下是前缀树的定义的C++代码示例:
```c++
class TrieNode {
public:
bool is_end; // 是否为字符串的结尾
TrieNode* children[26]; // 26个小写字母
TrieNode() {
is_end = false;
memset(children, NULL, sizeof(children)); // 初始化子节点为NULL
}
};
class Trie {
public:
TrieNode* root;
Trie() {
root = new TrieNode(); // 根节点不代表任何字符
}
void insert(string word) {
TrieNode* node = root;
for (char c : word) {
int index = c - 'a';
if (node->children[index] == NULL) {
node->children[index] = new TrieNode();
}
node = node->children[index];
}
node->is_end = true; // 标记字符串结尾
}
bool search(string word) {
TrieNode* node = root;
for (char c : word) {
int index = c - 'a';
if (node->children[index] == NULL) {
return false;
}
node = node->children[index];
}
return node->is_end; // 判断是否为字符串结尾
}
bool startsWith(string prefix) {
TrieNode* node = root;
for (char c : prefix) {
int index = c - 'a';
if (node->children[index] == NULL) {
return false;
}
node = node->children[index];
}
return true; // 只要前缀存在,就返回true
}
};
```
在上面的代码中,我们定义了一个`TrieNode`类表示前缀树的节点,它包含一个布尔型变量`is_end`表示该节点是否为字符串的结尾,以及一个大小为26的`children`数组,用于存储该节点的子节点。我们还定义了一个`Trie`类表示前缀树,它包含一个指向根节点的指针`root`,以及三个方法:`insert`用于插入字符串,`search`用于查找字符串,`startsWith`用于判断前缀是否存在。在插入字符串时,我们从根节点开始遍历,如果某个字符的子节点不存在,就创建一个新的子节点。在查找字符串和判断前缀是否存在时,我们也是从根节点开始遍历,如果某个字符的子节点不存在,就返回false。最后,如果遍历到字符串的结尾,我们判断该节点的`is_end`变量是否为true,以确定该字符串是否存在于前缀树中。
给我前缀树生成算法
前缀树(Trie树)是一种用于字典查找的数据结构,它可以高效地完成字符串的插入、删除和查找操作。下面是前缀树的生成算法:
1. 定义一个Trie节点类,包含一个指向子节点的指针数组和一个布尔变量表示该节点是否为单词结尾。
```
class TrieNode {
public:
TrieNode* children[26];
bool isEndOfWord;
TrieNode() {
for (int i = 0; i < 26; i++)
children[i] = NULL;
isEndOfWord = false;
}
};
```
2. 定义一个Trie类,包含一个根节点指针。在构造函数中初始化根节点。
```
class Trie {
public:
TrieNode* root;
Trie() {
root = new TrieNode();
}
};
```
3. 定义一个插入字符串的函数。从根节点开始,遍历待插入字符串的每个字符,如果当前字符对应的子节点不存在,则创建一个新的子节点,并将当前节点指向该子节点。最后将最后一个字符所对应的节点标记为单词结尾。
```
void insert(string word) {
TrieNode* node = root;
for (char ch : word) {
int index = ch - 'a';
if (node->children[index] == NULL)
node->children[index] = new TrieNode();
node = node->children[index];
}
node->isEndOfWord = true;
}
```
4. 定义一个查找字符串的函数。从根节点开始,遍历待查找字符串的每个字符,如果当前字符对应的子节点不存在,则返回false。如果查找完成后,最后一个字符所对应的节点为单词结尾,则返回true。
```
bool search(string word) {
TrieNode* node = root;
for (char ch : word) {
int index = ch - 'a';
if (node->children[index] == NULL)
return false;
node = node->children[index];
}
return node != NULL && node->isEndOfWord;
}
```
5. 定义一个以某个前缀开头的所有单词的函数。从根节点开始,遍历前缀字符串的每个字符,如果当前字符对应的子节点不存在,则返回空vector。如果遍历完成后,最后一个字符所对应的节点存在,则从该节点开始深度优先遍历整个子树,将遇到的所有单词加入结果vector中。
```
vector<string> startsWith(string prefix) {
vector<string> result;
TrieNode* node = root;
for (char ch : prefix) {
int index = ch - 'a';
if (node->children[index] == NULL)
return result;
node = node->children[index];
}
collectWords(node, prefix, result);
return result;
}
void collectWords(TrieNode* node, string prefix, vector<string>& result) {
if (node->isEndOfWord)
result.push_back(prefix);
for (int i = 0; i < 26; i++) {
if (node->children[i] != NULL) {
char ch = 'a' + i;
collectWords(node->children[i], prefix + ch, result);
}
}
}
```
这样,我们就完成了前缀树的生成算法。