Homework SourseThis is in Java Only use javautilScanner class Strictly you
This is in Java. Only use java.util.Scanner class. Strictly, you are NOT allowed to use any API classes for arrays, arraylists, queues, stacks and linkedlists. If you want to use them, you will have to write your own implementations for them.
In this problem, you will implement a data structure called a ‘trie’ as a ternary tree. Each node in a ternary tree can have at most three children nodes. The key inside each node is a character. The children of each node are the following:
left: contains a key that is less than the current node’s key, or null
equal: contains a key that is the next character in the string being stored, or null
right: contains a key that is more than the current node’s key, or null
Your objective is to write a program that inserts strings into a trie, prints the trie, and searches for strings in the trie. Implement the insert and search methods using recursion. That would mean, you need to write a public version of each method that calls the private version of the same method; the private version takes a TernaryNode as one of the method’s arguments. Write a menu driven interface for your program. An example output is shown below:
Ternary Tree Selection Menu:
1) Insert
2) Print (level-order)
3) Search
4) Exit
Enter your choice [1-4]: 1
Enter string to insert: beth
String ‘beth’ inserted
Enter your choice [1-4]: 1
Enter string to insert: bob
String ‘bob’ inserted
Enter your choice [1-4]: 1
Enter string to insert: james
String ‘james’ inserted
Enter your choice [1-4]: 1
Enter string to insert: carl
String ‘carl’ inserted
Enter your choice [1-4]: 2
Enter your choice [1-4]: 3
Enter string to search: barb
String ‘barb’ not found
Enter your choice [1-4]: 3
Enter string to search: bett
String ‘bett’ not found
Enter your choice [1-4]: 3
Enter string to search: carl
String ‘carl’ found
Enter your choice [1-4]: 3
Enter string to search: beob
String ‘beob’ not found
Enter your choice [1-4]: 3
Enter string to search: be
String ‘be’ not found
Enter your choice [1-4]: 3
Enter string to search: bob
String ‘bob’ found
Enter your choice [1-4]: 4
Bye!
Again, do NOT use any API classes for arrays, arraylists, queues, stacks and linkedlists. Write your own implementations for them if you want to use them.
--Level order traversal-- t o C a h b a m l sSolution
package com.dataStructureTST;
import java.util.ArrayList;
public class TernaryTree {
private TSTNode root;
private ArrayList<String> al;
/** Constructor **/
public TernaryTree()
{
root = null;
}
/** function to insert for a word **/
public void insert(String word)
{
root = insert(root, word.toCharArray(), 0);
}
/** function to insert for a word **/
public TSTNode insert(TSTNode r, char[] word, int ptr)
{
if (r == null)
r = new TSTNode(word[ptr]);
if (word[ptr] < r.data)
r.left = insert(r.left, word, ptr);
else if (word[ptr] > r.data)
r.right = insert(r.right, word, ptr);
else
{
if (ptr + 1 < word.length)
r.equal = insert(r.equal, word, ptr + 1);
else
r.isEnd = true;
}
return r;
}
/** function to search for a word **/
public String search(String word)
{
return search(root, word.toCharArray(), 0);
}
/** function to search for a word **/
private String search(TSTNode r, char[] word, int ptr)
{
if (r == null)
return \"not found\";
if (word[ptr] < r.data)
return search(r.left, word, ptr);
else if (word[ptr] > r.data)
return search(r.right, word, ptr);
else
{
if (r.isEnd && ptr == word.length - 1)
return \"found\";
else if (ptr == word.length - 1)
return \"not found\";
else
return search(r.equal, word, ptr + 1);
}
}
/** function to print tree **/
public String toString()
{
al = new ArrayList<String>();
traverse(root, \"\");
return \"\ Ternary Search Tree : \"+ al;
}
/** function to traverse tree **/
private void traverse(TSTNode r, String str)
{
if (r != null)
{
traverse(r.left, str);
str = str + r.data;
if (r.isEnd)
al.add(str);
traverse(r.equal, str);
str = str.substring(0, str.length() - 1);
traverse(r.right, str);
}
}
}
package com.dataStructureTST;
public class TSTNode {
char data;
boolean isEnd;
TSTNode left, equal, right;
/** Constructor **/
public TSTNode(char data)
{
this.data = data;
this.isEnd = false;
this.left = null;
this.equal = null;
this.right = null;
}
}
//This is test class to execute above code
package com.dataStructureTST;
import java.util.Scanner;
public class UserTest {
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of TernarySearchTree */
TernaryTree tst = new TernaryTree();
System.out.println(\"Ternary Search Tree Test\ \");
/* Perform tree operations */
System.out.println(\"\ Ternary Search Tree Operations\ \");
System.out.println(\"1. Insert\");
System.out.println(\"2. Print(Level Order)\");
System.out.println(\"3. Search word\");
System.out.println(\"4. Exit\");
while(true){
//System.out.println(\"\ Ternary Search Tree Operations\ \");
/*System.out.println(\"1. insert word\");
System.out.println(\"2. search word\");
System.out.println(\"3. delete word\");
System.out.println(\"4. check empty\");
System.out.println(\"5. make empty\");*/
System.out.println(\"Enter your choice [1-4]:\");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println(\"Enter String to insert\");
tst.insert( scan.next() );
break;
case 2 :
System.out.println(\"-----Level Order Traversal-----\");
System.out.println(tst);
break;
case 3 :
System.out.println(\"Enter String to search\");
System.out.println(\"Search result : \"+ tst.search( scan.next() ));
break;
case 4 :
System.out.println(\"Bye\");
System.exit(0);
break;
default :
System.out.println(\"Wrong Entry \ \");
break;
}
}
}
}
Output:
Ternary Search Tree Test
Ternary Search Tree Operations
1. Insert
2. Print(Level Order)
3. Search word
4. Exit
Enter your choice [1-4]:
1
Enter String to insert:
beth
Enter your choice [1-4]:
1
Enter String to insert:
bob
Enter your choice [1-4]:
1
Enter String to insert:
carl
Enter your choice [1-4]:
2
-----Level Order Traversal-----
Ternary Search Tree : [beth, bob, carl]
Enter your choice [1-4]:
3
Enter String to search:
cat
Search result :String not found
Enter your choice [1-4]:
3
Enter String to search:
bob
Search result :String found
Enter your choice [1-4]:
4
Bye
