Key Features of a Trie
- Node Structure: Each node in the Trie contains an array of pointers (one for each character) and a boolean flag to indicate if the node marks the end of a valid word.
- Insertion: To insert a word, you traverse down the Trie, creating new nodes as needed for each character.
- Search: To search for a word, you follow the path down the Trie according to the characters in the word.
- Prefix Search: You can also search for all words that start with a given prefix.
C Program to Implement a Trie Data Structure
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define ALPHABET_SIZE 26 // Assuming only lowercase letters a-z
#define MAX_WORD_LENGTH 100 // Maximum length for a word
// Trie node structure
struct TrieNode {
struct TrieNode* children[ALPHABET_SIZE];
bool isEndOfWord; // True if the node represents the end of a word
};
// Function to create a new Trie node
struct TrieNode* createNode() {
struct TrieNode* newNode = (struct TrieNode*)malloc(sizeof(struct TrieNode));
newNode->isEndOfWord = false;
for (int i = 0; i < ALPHABET_SIZE; i++) {
newNode->children[i] = NULL; // Initialize all children to NULL
}
return newNode;
}
// Function to insert a word into the Trie
void insert(struct TrieNode* root, const char* word) {
struct TrieNode* currentNode = root;
while (*word) {
int index = *word - 'a'; // Calculate index for the current character
if (!currentNode->children[index]) {
currentNode->children[index] = createNode(); // Create new node if it doesn't exist
}
currentNode = currentNode->children[index]; // Move to the next node
word++; // Move to the next character
}
currentNode->isEndOfWord = true; // Mark the end of the word
}
// Function to search for a word in the Trie
bool search(struct TrieNode* root, const char* word) {
struct TrieNode* currentNode = root;
while (*word) {
int index = *word - 'a';
if (!currentNode->children[index]) {
return false; // If the character doesn't exist, word not found
}
currentNode = currentNode->children[index];
word++;
}
return currentNode->isEndOfWord; // Return true if it's the end of a valid word
}
// Function to check if there is any word in the Trie that starts with the given prefix
bool startsWith(struct TrieNode* root, const char* prefix) {
struct TrieNode* currentNode = root;
while (*prefix) {
int index = *prefix - 'a';
if (!currentNode->children[index]) {
return false; // If the prefix doesn't exist, return false
}
currentNode = currentNode->children[index];
prefix++;
}
return true; // Prefix found
}
// Main function to demonstrate the Trie operations
int main() {
struct TrieNode* root = createNode(); // Create the root node
int choice;
char word[MAX_WORD_LENGTH];
// Interactive menu for Trie operations
while (1) {
printf("1. Insert a word\n");
printf("2. Search for a word\n");
printf("3. Check for a prefix\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
getchar(); // Consume newline character
switch (choice) {
case 1:
printf("Enter a word to insert: ");
fgets(word, sizeof(word), stdin);
word[strcspn(word, "\n")] = '\0'; // Remove newline character
insert(root, word);
printf("Inserted: %s\n", word);
break;
case 2:
printf("Enter a word to search: ");
fgets(word, sizeof(word), stdin);
word[strcspn(word, "\n")] = '\0'; // Remove newline character
printf("Searching for '%s': %s\n", word, search(root, word) ? "Found" : "Not Found");
break;
case 3:
printf("Enter a prefix to check: ");
fgets(word, sizeof(word), stdin);
word[strcspn(word, "\n")] = '\0'; // Remove newline character
printf("Prefix '%s': %s\n", word, startsWith(root, word) ? "Exists" : "Does not exist");
break;
case 4:
printf("Exiting...\n");
free(root); // Free the allocated memory
return 0;
default:
printf("Invalid choice. Please try again.\n");
}
}
return 0;
}
Explanation of the Updated Code
- User Interaction:
- The program now presents a simple menu for the user to choose from inserting a word, searching for a word, checking a prefix, or exiting.
- The user can input words and prefixes directly, making it more interactive.
- Input Handling:
fgetsis used to read strings, allowing for spaces in input. The newline character is removed usingstrcspnto ensure the strings are formatted correctly.
- Dynamic Operations:
- The Trie operations remain the same (insert, search, prefix checking), but now they respond to user inputs in real-time.
How to Run the Program
- Compile the code using a C compiler (e.g.,
gcc):Copy codegcc trie.c -o trie - Run the compiled program:bashCopy code
./trie - Follow the prompts to insert words, search for them, and check prefixes.
Sample Input and Output
Here’s how a sample interaction with the program might look:
mathematicaCopy code1. Insert a word
2. Search for a word
3. Check for a prefix
4. Exit
Enter your choice: 1
Enter a word to insert: hello
Inserted: hello
1. Insert a word
2. Search for a word
3. Check for a prefix
4. Exit
Enter your choice: 1
Enter a word to insert: hi
Inserted: hi
1. Insert a word
2. Search for a word
3. Check for a prefix
4. Exit
Enter your choice: 2
Enter a word to search: hello
Searching for 'hello': Found
1. Insert a word
2. Search for a word
3. Check for a prefix
4. Exit
Enter your choice: 3
Enter a prefix to check: he
Prefix 'he': Exists
1. Insert a word
2. Search for a word
3. Check for a prefix
4. Exit
Enter your choice: 4
Exiting...
Conclusion
This updated implementation of the Trie allows for dynamic interaction and showcases the functionalities effectively. You can test various words and prefixes, making it a practical tool for understanding how Tries work.
