TRIES
Program Coding:
import java.io.*;
class node
{
char content;
boolean marker;
node[] child;
public node()
{
marker=false;
child=new
node[26];
}
public node(int i)
{
content=(char)((int)'a'+i);
marker=false;
child=new
node[26];
}}
class trie
{
private node root;
public trie()
{
root=new
node();
root.content='
';
}
public void insert(String s)
{
node current=root;
if(s.length()==0)
current.marker=true;
for(int
i=0;i<s.length();i++)
{
if(current.child[(int)(s.charAt(i)-'a')]!=null)
{
current=current.child[(int)(s.charAt(i)-'a')];
System.out.println("Inserted
character:"+current.content);
}
else
{
current.child[(int)(s.charAt(i)-'a')]=new
node((int)(s.charAt(i)-'a'));
current=current.child[(int)(s.charAt(i)-'a')];
System.out.println("Inserted
character:"+current.content);
}
if(i==s.length()-1)
current.marker=true;
}
System.out.println("finished
inserting the word:"+s+"\n");
}
public boolean
search(String s)
{
node
current=root;
System.out.println("\nSearching
for string:"+s);
while(current!=null)
{
for(int
i=0;i<s.length();i++)
{
if(current.child[(int)(s.charAt(i)-'a')]==null)
{
System.out.println("cannot
find string:"+s);
return
false;
}
else
{
current=current.child[(int)(s.charAt(i)-'a')];
System.out.println("Found
character:"+current.content);
}}
if(current.marker==true)
{
System.out.println("Found
string:"+s);
return
true;
}
else
{
System.out.println("cannot
find string:"+s+"(only present as a substring)");
return
false;
}}
return false;
}
}
public class testtrie1
{
public static void
main(String[] args)throws IOException
{
trie
o=new trie();
String ele;
int choice,n;
DataInputStream
obj=new DataInputStream(System.in);
do
{
System.out.println("1.Insert");
System.out.println("2.search");
System.out.println("3.Exit");
System.out.println("Enter
your choice:");
choice=Integer.parseInt(obj.readLine());
switch(choice)
{
case
1:
System.out.println("Enter
the maximun number of elements:");
n=Integer.parseInt(obj.readLine());
for(int
i=0;i<n;i++)
{
System.out.println("Enter
the element");
ele=obj.readLine();
o.insert(ele);
}
break;
case
2:
System.out.println("Enter
the element to search:");
String
se=obj.readLine();
System.out.println("After
searching the element !!!");
o.search(se);
break;
case
3:
break;
}
}while(choice<3);
}
}
Output:
TRIES
1. Insert
2.Search
3.Exit
Enter your choice:
1
Enter the maximun number of
elements:
3
Enter the element
cat
Inserted character:c
Inserted character:a
Inserted character:t
finished inserting the word:cat
Enter the element
bat
Inserted character:b
Inserted character:a
Inserted character:t
finished inserting the word:bat
Enter the element
kite
Inserted character:k
Inserted character:i
Inserted character:t
Inserted character:e
finished inserting the word:kite
1.Insert
2.search
3.Exit
Enter your choice:
2
Enter the element to search:
cat
After searching the element !!!
Searching for string:cat
Found character:c
Found character:a
Found character:t
Found string:cat
1.Insert
2.search
3.Exit
Enter your choice:3
No comments:
Post a Comment