给我前缀树生成算法
时间: 2023-08-04 08:11:39 浏览: 45
前缀树(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);
}
}
}
```
这样,我们就完成了前缀树的生成算法。