This is in java. Create a program that stores the name like a trie would and the
ID: 3792894 • Letter: T
Question
This is in java. Create a program that stores the name like a trie would and then be able to insert names into it, allow searches for name, and print the level order
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
Here is an example, on how to create a trie to store a set of strings:
Strings: {beth, bob, james, carl, tom, terry, luke, barb, bailey, bernie, barney}
Insert string ”beth”. Initially root is empty. So, ‘b’ is inserted as the root, ‘e’ is inserted as equal-child of ‘b’, ‘t’ is inserted as equal-child of ‘e’, and, lastly, ‘h’ is inserted as equal-child of ‘t’.
B b b b
| | |
e e e
| |
t t
|
h
Next, for the string “bob”, we start at root of tree, ‘b’. The first character of bob(‘b’) is already the root, so we do not insert another node for ‘b’. We go to the second character of bob (‘o’). To insert ‘o’, we go down the equal-child of ‘b’ (which is ‘e’). ‘o’ > ‘e’, so we go down right subtree of ‘e’. Because right subtree of ‘e’ is null, we insert ‘o’ as right child of ‘e’. After that, We go to the third character of bob (‘b’); ‘b’ becomes equal-child of ‘o’.
B b b
| | |
E e e
| | |
T t o t o
| | | | |
H h h b
Next, we insert string “james”; we start again at root of tree, which is ‘b’. ‘j’ > ‘b’. So, we go down right subtree of ‘b’. Because right child of ‘b’ is null, we insert ‘j’ a right-child of ‘b’. ‘a’, ‘m’, ‘e’ and ‘s’ are then inserted equal-children (successively) below ‘j’
B
|
e
|
t
|
h
One more example, insert ‘carl’. We start at the root of the tree, which is ‘b’. ‘c’ > ‘b’, so we go down right subtree of ‘b’ and reach ‘j’. ‘c’< ‘j’, so we go down left subtree of ‘j’. This left subtree of ‘j’ is null, and we insert ‘c’ as left child of ‘j’. ‘a’, ‘r’ and ‘l’ are then inserted as equal-children (successively) below ‘c’
The rest of the strings are inserted below
To lookup or search for a string in a trie, you start at the root. Depending on the character of the string being searched for go down the left, equal or right child at each node. Note that to find a string successfully, the number of equal edges traversed should be equal to the number of characters in the string less 1.
Your objective is to write a program that inserts strings into a trie, prints the trie, and searches for strings in the trie. As we did in class for the Binary Search Tree code, it would be easier to 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. As before, you have to write a menu driven interface for your program. An example output is shown below
Ternary Tree Selection Menu:
Insert
Print (level-order)
Search
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
--Level order traversal--
b
e j
t o c a
h b a m
r e
l s
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!
Explanation / Answer
Following is Java program stores the name like a trie would and then be able to insert names into it, allow searches for name, and print the level order. (Please let me know in case of any query.)
Ternary Tree Selection Menu:
1. Insert
2. Print (level-order)
3. Search
4. Exit
Java Program Code:
import java.util.Scanner;
/**
*
*
*/
public class TernaryTreeDriver {
public static void main(String[] args) {
try (Scanner scan = new Scanner(System.in)) {
TernaryTree ternaryTree = new TernaryTree();
System.out.println("Ternary Tree Driver ");
System.out.println(showManu());
while (true) {
System.out.println("Enter your choice [1-4]: ");
int choice = scan.nextInt();
if (4 == choice) {
System.out.println("Bye!");
break;
}
switch (choice) {
case 1:
System.out.println("Enter string to insert: ");
String insertString = scan.next();
ternaryTree.insert(insertString);
System.out.println("String '" + insertString + "' inserted ");
break;
case 2:
System.out.println("--Level order traversal-- ");
ternaryTree.printLevelOrder();
break;
case 3:
System.out.println("Enter string to search: ");
String searchString = scan.next();
if (ternaryTree.search(searchString)) {
System.out.println("String '" + searchString + "' found ");
} else {
System.out.println("String '" + searchString + "' not found ");
}
break;
default:
System.out.println("Wrong choice. Please try again! ");
break;
}
}
}
}
private static String showManu() {
return "Ternary Tree Selection Menu: 1. Insert 2. Print (level-order) 3. Search 4. Exit";
}
}
/**
* This class holds ternary tree node
*
*/
class TernaryTreeNode {
char key;
boolean isEnd;
TernaryTreeNode left, equal, right;
/** Constructor **/
public TernaryTreeNode(char key) {
this.key = key;
this.isEnd = false;
this.left = null;
this.equal = null;
this.right = null;
}
}
/**
* TernaryTree class
*
*/
class TernaryTree {
private TernaryTreeNode root;
/**
* Method to insert for a string word
* @param word
*/
public void insert(String word) {
root = insert(root, word.toCharArray(), 0);
}
private TernaryTreeNode insert(TernaryTreeNode ternaryTreeNode, char[] word, int ptr) {
if (ternaryTreeNode == null) {
ternaryTreeNode = new TernaryTreeNode(word[ptr]);
}
if (word[ptr] < ternaryTreeNode.key) {
ternaryTreeNode.left = insert(ternaryTreeNode.left, word, ptr);
} else if (word[ptr] > ternaryTreeNode.key) {
ternaryTreeNode.right = insert(ternaryTreeNode.right, word, ptr);
} else {
if (ptr + 1 < word.length) {
ternaryTreeNode.equal = insert(ternaryTreeNode.equal, word, ptr + 1);
} else {
ternaryTreeNode.isEnd = true;
}
}
return ternaryTreeNode;
}
/**
* Method to search for a string word
* @param word
* @return
*/
public boolean search(String word) {
return search(root, word.toCharArray(), 0);
}
private boolean search(TernaryTreeNode ternaryTreeNode, char[] word, int ptr) {
if (ternaryTreeNode == null) {
return false;
}
if (word[ptr] < ternaryTreeNode.key) {
return search(ternaryTreeNode.left, word, ptr);
} else if (word[ptr] > ternaryTreeNode.key) {
return search(ternaryTreeNode.right, word, ptr);
} else {
if (ternaryTreeNode.isEnd && ptr == word.length - 1) {
return true;
} else if (ptr == word.length - 1) {
return false;
} else {
return search(ternaryTreeNode.equal, word, ptr + 1);
}
}
}
/**
* Method to print level order traversal of ternary tree
*/
void printLevelOrder(){
int height = height(root);
int level;
for (level=1; level<=height; level++){
printGivenLevel(root, level);
System.out.print(" ");
}
}
/**
* Method to print given level
* @param ternaryTreeNode
* @param level
*/
private void printGivenLevel (TernaryTreeNode ternaryTreeNode ,int level){
if (ternaryTreeNode == null)
return;
if (level == 1){
System.out.print(ternaryTreeNode.key + " ");
}else if (level > 1){
printGivenLevel(ternaryTreeNode.left, level-1);
printGivenLevel(ternaryTreeNode.equal, level-1);
printGivenLevel(ternaryTreeNode.right, level-1);
}
}
/**
* Method to calculate ternary tree height
* @param ternaryTreeNode
* @return
*/
private int height(TernaryTreeNode ternaryTreeNode){
if (ternaryTreeNode == null){
return 0;
}else{
//compute height of each subtree
int lheight = height(ternaryTreeNode.left);
int eheight = height(ternaryTreeNode.equal);
int rheight = height(ternaryTreeNode.right);
if( lheight>=eheight && lheight>=rheight){
return(lheight+1);
}else if (eheight>=lheight && eheight>=rheight){
return(eheight+1);
}else{
return(rheight+1);
}
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.