Tries

•  The standard Trie for a set of strings S is an ordered tree such that:

•   Each node but the root is labeled with a character 
• The children of a node are alphabetically ordered 
• The paths from the external nodes to the root yield the strings of S

•   Example: standard Trie for the set of strings

Java Code:

/* Implementation of Trie using JAVA
Date:         18/11/2012
Author :     Sarju S
*/
import java.io.*;
class TrieNode
{
    char letter;
    TrieNode[] links;
    boolean fullWord;
  
    TrieNode(char letter, boolean fullWord)
    {
        this.letter = letter;
        links = new TrieNode[26];//For storing 26 English Alphabets
        this.fullWord = fullWord;
    }
}
public class Trie
{   
    /*Function for creating Empty Trie*/
    static TrieNode createTree()
    {
        return(new TrieNode('\0', false));
    }
   /*Function for insertion into Trie*/
    static void insertWord(TrieNode root, String word)
    {
        int offset = 97;//ASCII Value of 'a'
        int l = word.length();
        char[] letters = word.toCharArray();
        TrieNode curNode = root;
      
        for (int i = 0; i < l; i++)
        {
            if (curNode.links[letters[i]-offset] == null)
                curNode.links[letters[i]-offset] = new TrieNode(letters[i], i == l-1 ? true : false);
            curNode = curNode.links[letters[i]-offset];
        }
    }
     /*Function for search a particular word from Trie*/
    static boolean find(TrieNode root, String word)
    {
        char[] letters = word.toCharArray();
        int l = letters.length;
        int offset = 97;//ASCII Value of 'a'
        TrieNode curNode = root;
      
        int i;
        for (i = 0; i < l; i++)
        {
            if (curNode == null)
                return false;
            curNode = curNode.links[letters[i]-offset];
        }
      
        if (i == l && curNode == null)
            return false;
      
        if (curNode != null && !curNode.fullWord)
            return false;
      
        return true;
    }
    /*Function for Printing Trie*/
    static void printTree(TrieNode root, int level, char[] branch)
    {
        if (root == null)
            return;
      
        for (int i = 0; i < root.links.length; i++)
        {
            branch[level] = root.letter;
            printTree(root.links[i], level+1, branch);  
        }
      
        if (root.fullWord)
        {
            for (int j = 1; j <= level; j++)
                System.out.print(branch[j]);
            System.out.println();
        }
    }
  
    public static void main(String[] args)
    {
        TrieNode tree = createTree();
           String words,searchWord;
        int choice;
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        try{
            do{
                System.out.print("\nMENU\n1:Insert\n2.Search\n3.Print\n4.Exit\n");
                System.out.println("Enter Your Choice:");
                choice = Integer.parseInt(in.readLine());
                switch(choice){
                    case 1:    System.out.println("Enter the word to insert :");
                            words = in.readLine();
                            insertWord(tree, words);
                            break;
                    case 2:    System.out.println("Enter the word to search :");
                            searchWord = in.readLine();
                             if (find(tree, searchWord))
                                System.out.println("The word was found");
                             else
                                System.out.println("The word was NOT found");
                            break;
                    case 3:    char[] branch = new char[50];
                            System.out.println("The Trie");
                            printTree(tree, 0, branch);
                    }
                }while(choice<4 br="br">            }
        catch(Exception e){
        }
       
    }
}

 OUPUT

C:\Users\Sarju>javac trie.java

C:\Users\Sarju>java Trie

MENU
1:Insert
2.Search
3.Print
4.Exit
Enter Your Choice:
1
Enter the word to insert :
sss

MENU
1:Insert
2.Search
3.Print
4.Exit
Enter Your Choice:
1
Enter the word to insert :
www

MENU
1:Insert
2.Search
3.Print
4.Exit
Enter Your Choice:
3
The Trie
sss
www

MENU
1:Insert
2.Search
3.Print
4.Exit
Enter Your Choice:
2
Enter the word to search :
kkk
The word was NOT found

MENU
1:Insert
2.Search
3.Print
4.Exit
Enter Your Choice:4

C:\Users\Sarju>

                For More Details : Click Here