trie树 插入删除查找c语言实现
时间: 2024-09-21 18:12:39 浏览: 32
Trie树(也称为字典树或前缀树)是一种用于存储字符串数据的数据结构,每个节点代表一个字符,从根到某个节点的路径表示一个字符串。插入、删除和查找操作在Trie树上通常比较高效,特别是对于前缀搜索。
以下是简单的C语言实现Trie树的插入、删除和查找操作:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct TrieNode {
char val;
struct TrieNode* children[26]; // 对于ASCII码,假设只处理小写字母
bool isEndOfWord;
} TrieNode;
TrieNode* createNode() {
TrieNode* newNode = (TrieNode*)malloc(sizeof(TrieNode));
newNode->isEndOfWord = false;
for (int i = 0; i < 26; i++) {
newNode->children[i] = NULL;
}
return newNode;
}
// 插入单词到Trie树
void insert(TrieNode** root, const char* word) {
TrieNode* current = *root;
for (char c : word) {
if (!current- 'a']) {
current->children[c - 'a'] = createNode();
}
current = current->children[c - 'a'];
}
current->isEndOfWord = true;
}
// 查找单词是否在Trie树中
bool search(TrieNode* root, const char* word) {
TrieNode* current = root;
for (char c : word) {
if (!current->children[c - 'a']) {
return false;
}
current = current->children[c - 'a'];
}
return current->isEndOfWord;
}
// 删除单词(这里简化了实现,仅支持直接删除空节点)
void delete(TrieNode** root, const char* word) {
TrieNode* current = *root;
bool found = search(current, word);
if (!found || !current->isEndOfWord) {
return;
}
deleteHelper(current, word, 0); // 使用递归辅助函数删除
if (current->isEndOfWord && isEmpty(current)) { // 当前节点及其所有子节点都是空的,则删除当前节点
free(current);
*root = NULL;
}
}
// 辅助函数:递归删除节点
void deleteHelper(TrieNode* current, const char* word, int index) {
if (index == strlen(word)) {
current->isEndOfWord = false;
} else {
if (search(current->children, word + index)) {
deleteHelper(current->children[word[index] - 'a'], word, index + 1);
}
if (!current->isEndOfWord && isEmpty(current)) {
free(current);
current = NULL;
}
}
}
// 判断节点是否为空
bool isEmpty(TrieNode* node) {
for (int i = 0; i < 26; i++) {
if (node->children[i]) {
return false;
}
}
return true;
}
// 示例使用
int main() {
TrieNode* root = createNode();
insert(&root, "apple");
insert(&root, "app");
printf("Search \"app\": %s\n", search(root, "app") ? "Found" : "Not Found");
delete(&root, "apple"); // 删除"apple"
printf("Search \"apple\" after deletion: %s\n", search(root, "apple") ? "Found" : "Not Found");
return 0;
}
```
以上代码实现了基本的Trie树操作,但在实际应用中可能需要考虑更多细节,例如处理大小写、特殊字符等。注意,删除功能在此示例中相对简单,仅适用于直接删除空节点的情况,实际情况可能会更复杂。