How do i code up a trie implemention with 4 children as an a

How do i code up a trie implemention with 4 children as an array and at the same time store a key and value in each children ? Java

Solution

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <stdbool.h>

#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])

#define ALPHABET_SIZE (26)

#define CHAR_TO_INDEX(c) ((int)c - (int)\'a\')

struct TrieNode

{

    struct TrieNode *children[ALPHABET_SIZE];

    bool isLeaf;

};

struct TrieNode *getNode(void)

{

    struct TrieNode *pNode = NULL;

    pNode = (struct TrieNode *)malloc(sizeof(struct TrieNode));

    if (pNode)

    {

        int i;

        pNode->isLeaf = false;

        for (i = 0; i < ALPHABET_SIZE; i++)

            pNode->children[i] = NULL;

    }

    return pNode;

}

void insert(struct TrieNode *root, const char *key)

{

    int level;

    int length = strlen(key);

    int index;

    struct TrieNode *pCrawl = root;

    for (level = 0; level < length; level++)

    {

        index = CHAR_TO_INDEX(key[level]);

        if (!pCrawl->children[index])

            pCrawl->children[index] = getNode();

        pCrawl = pCrawl->children[index];

    }

        pCrawl->isLeaf = true;

}

bool search(struct TrieNode *root, const char *key)

{

    int level;

    int length = strlen(key);

    int index;

    struct TrieNode *pCrawl = root;

    for (level = 0; level < length; level++)

    {

        index = CHAR_TO_INDEX(key[level]);

        if (!pCrawl->children[index])

            return false;

        pCrawl = pCrawl->children[index];

    }

    return (pCrawl != NULL && pCrawl->isLeaf);

}

int main()

{

    // Input keys (use only \'a\' through \'z\' and lower case)

    char keys[][8] = {\"the\", \"a\", \"there\", \"answer\", \"any\",

                     \"by\", \"bye\", \"their\"};

    char output[][32] = {\"Not present in trie\", \"Present in trie\"};

    struct TrieNode *root = getNode();

    

    int i;

    for (i = 0; i < ARRAY_SIZE(keys); i++)

        insert(root, keys[i]);

    printf(\"%s --- %s\ \", \"the\", output[search(root, \"the\")] );

    printf(\"%s --- %s\ \", \"these\", output[search(root, \"these\")] );

    printf(\"%s --- %s\ \", \"their\", output[search(root, \"their\")] );

    printf(\"%s --- %s\ \", \"thaw\", output[search(root, \"thaw\")] );

    return 0;

}