Showing posts with label Trie. Show all posts
Showing posts with label Trie. Show all posts

Thursday, August 23, 2012

Inserting into Trie and Checking if an element is present in the Trie



// INPUT : char *str[] = { "one$", "two$", "three$", "four$", 
//                         "thre$" };
//         char *test[] = { "one$", "too$", "three$", "fore$" };
// OUTPUT : one$ is present, too$ is not present, three$ is 
//          present, fore$ is not present



#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define ASIZE 255

typedef struct node {
    struct node *a[ASIZE];
} Node;

Node *newNode()
{
    Node *n = (Node *) malloc(sizeof(Node));
    int i;
    for (i = 0; i < ASIZE; i++) {
n->a[i] = NULL;
    }
    return n;
}

void insertTrie(Node ** rootRef, char *str)
{
    int len = strlen(str);
    int i;
    Node *root = *rootRef;
    if (root == NULL) {
root = newNode();
*rootRef = root;
    }
    for (i = 0; i < len; i++) {
int p = str[i];
if (root->a[p] == NULL) {
   root->a[p] = newNode();
}
root = root->a[p];
    }
}

int isPresent(Node * root, char *str)
{
    int len = strlen(str);
    int i;
    int isPresent = 1;
    for (i = 0; i < len; i++) {
int p = str[i];
if (root->a[p] == NULL) {
   isPresent = 0;
   break;
} else {
   root = root->a[p];
}
    }
    return isPresent;
}

printAllWordsRecur(Node *root,char *out,int len){
int i;
int done = 1;
for(i=0;i<ASIZE;i++){
if(root->a[i] == NULL){
continue;
} else{
done = 0;
out[len++] = i;
printAllWordsRecur(root->a[i],out,len);
len--;
}
}
if(done){
out[len] = '\0';
printf("%s\n",out);
}
}

printAllWords(Node *root){
static char out[50];
printAllWordsRecur(root,out,0);
}

int main()
{
    char *str[] = { "one$", "two$", "three$", "four$", "thre$" };
    char *test[] = { "one$", "too$", "three$", "fore$" };
    Node *root = NULL;
    int i;
    for (i = 0; i < 5; i++) {
insertTrie(&root, str[i]);
    }
    for (i = 0; i < 4; i++) {
if (isPresent(root, test[i])) {
   printf("%s is present\n", test[i]);
} else {
   printf("%s is not present\n", test[i]);
}
    }
    printAllWords(root);
    return 0;
}