Language: C99 You must complete the implementation of a trie data structure (pro

Question

Language: C99

You must complete the implementation of a trie data structure (pronounced "try"), a tree where each node has 26 children (corresponding to the 26 letters of the alphabet).

To understand a trie, it is best to see a concrete example. Note that empty boxes are either false or NULL.

To see how the word "ace" is stored, consider that the first letter of the word is 'a', which is also the first letter of the alphabet. From the root node, we follow the first child link to the next node. This node is part of words that start with the letter 'a'. Because the string "a" is contained in the trie, the value of end_word at this node is TRUE (filled in). You can think of this as corresponding to the null terminator for the word "a". The next letter in the word "ace" is 'c' (third letter of the alphabet) and so we follow the third child to the next node. The word "ac" is not a valid word, so the value of end_word here is false. Because the next letter 'e' is the fifth letter of the alphabet, we follow the fifth child. There are no additional letters in the word "ace", so the end_word at this node is TRUE to indicate that word "ace" ends there.

As an exercise, review how "zoo" is similarly stored.

We can now make a few observations about the structure of the tree. Each leaf in the tree must have end_word be true, and all of its children must be NULL, otherwise it would not be a valid leaf. Also, if the value of end_word is true at the root, then the empty string ""is contained in the trie. If there are no words in the trie, then the value of root would be NULL.

Write the following functions:

// A word only contains lowercase letters ('a'...'z')
// an empty string ("") is also considered a word

// requirements: ALL string and trie parameters are valid (non-NULL)
// string parameters are words

struct trienode {
bool word_end;
struct trienode *children[26];
};

struct trie {
struct trienode *root;
};

// trie_destroy(t) frees all memory for t
// effects: t is no longer valid
// time: O(n), n is the number of characters in all of the words in t
void trie_destroy(struct trie *t);

// trie_print(t) prints each word in trie t in alphabetical order,
// with each word on a newline
// effects: displays output (if t is not empty)
// time: O(n), n is the number of characters in all of the words in t
void trie_print(const struct trie *t);

// trie_to_aos(t) generates a new array containing all of the words
// in trie t in alphabetical order, each word is a new string
// notes: returns NULL if t is empty
// use trie_count(t) to determine the length of the array
// effects: allocates memory (caller must free all strings and the array)
// time: O(n), n is the number of characters in all of the words in t
char **trie_to_aos(const struct trie *t);

// trie_count(t) determines how many words are in t
// time: O(n), n is the number of characters in all of the words in t
int trie_count(const struct trie *t);

root endword - end word end word end word end word end word end word

Explanation / Answer

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

public class Trie {

// Alphabet size (# of symbols)

static final int ALPHABET_SIZE = 26;

// trie node

static class TrieNode

{

TrieNode[] children = new TrieNode[ALPHABET_SIZE];

  

// isEndOfWord is true if the node represents

// end of a word

boolean isEndOfWord;

TrieNode(){

isEndOfWord = false;

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

children[i] = null;

}

};

  

static TrieNode root;

public void Trie()

{

root=new TrieNode();

}

// Returns true if word presents in trie, else false

public static boolean contains(String word)

{

int level;

int length = word.length();

int index;

TrieNode pCrawl = root;

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

{

index = word.charAt(level) - 'a';

  

if (pCrawl.children[index] == null)

return false;

  

pCrawl = pCrawl.children[index];

}

  

return (pCrawl != null && pCrawl.isEndOfWord);

}

// If not present, inserts word into trie

// If the word is prefix of trie node,

// just marks leaf node

public static boolean add(String word)

{

if(contains(word))return false;

int level;

int length = word.length();

int index;

  

TrieNode pCrawl = root;

  

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

{

index = word.charAt(level) - 'a';

if (pCrawl.children[index] == null)

pCrawl.children[index] = new TrieNode();

  

pCrawl = pCrawl.children[index];

}

  

// mark last node as leaf

pCrawl.isEndOfWord = true;

return true;

}

// Returns true if pre is prefix of a word in trie, else false

public static boolean containsPrefix(String pre)

{

int level;

int length = pre.length();

int index;

TrieNode pCrawl = root;

  

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

{

index = pre.charAt(level) - 'a';

  

if (pCrawl.children[index] == null)

return false;

  

pCrawl = pCrawl.children[index];

}

  

return (pCrawl != null);

}

// Function to count number of words

public static int wordCount(TrieNode root)

{

int result = 0;

  

// Leaf denotes end of a word

if (root.isEndOfWord)

result++;

  

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

if (root.children[i] != null )

result += wordCount(root.children[i]);

return result;

}

//Return number of word in TRIE

public static int size()

{

return wordCount(root);

}

//Clears the TRIE

public static void clear()

{

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

root.children[i]=null;

}

public static void main (String[] args) throws java.lang.Exception

{

root=new TrieNode();

add("hello");

add("hell");

System.out.println(contains("hello"));

System.out.println("Total number of Words "+size());

System.out.println(containsPrefix("he"));

}

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.