Please do not use any Java pre-defined classes. We are only able to use Java.uti
ID: 3795912 • Letter: P
Question
Please do not use any Java pre-defined classes. We are only able to use Java.util.Scanner;
DO NOT USE use Java API (list/stack/queue/ array) classes.
We are to write a Java program.
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!
Please do not use any Java pre-defined classes. We are only able to use Java.util.Scanner;
--Level order traversal-- t o C a h b a m l sExplanation / Answer
Below is the code for java implementation for ternary tree