(In Java): The assignment is... Write a TrieSpellChecker class that supports the
ID: 3819379 • Letter: #
Question
(In Java): The assignment is... Write a TrieSpellChecker class that supports the same functionality as your BSTSpellChecker. Specifically, it should include the following methods:
a. void add(String s) Adds the specified word to the trie.
b. boolean contains(String s) Returns whether the specified word is in the trie.
c. A method that reads a list of words from a file and adds them all into the trie. In a trie, the order in which the words are added should not matter.
Definition of BST Class: The BSTSpellChecker class should have an instance variable of type BinarySearchTree to store its word list. You can use the BinarySearchTree code that we wrote in lecture. BSTSpellChecker should contain the following methods:
a. void add(String s) Adds the specified word to the tree.
b. boolean contains(String s) Returns whether the specified word is in the tree.
c. A method that reads a list of words from a file and adds them all into the tree. Add the words to the tree in the same order that they appear in the file (i.e., alphabetically). (Note – you will probably have to use non-recursive versions of the BST add and find methods to prevent stack overflows here!)
d. Remember that adding things in order into a BST is a bad idea – this will result in a linked list with O(n) performance. Write another version of the above method that adds the words in a balanced manner. You can do this by first adding the word in the middle of the file, then recursively adding the words in the middle of the left and right halves, and so on.
Explanation / Answer
package chegg.bstree;
/*
* Java Program to Implement Binary Search Tree
*/
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
class BinarySearchTree {
private Node root;
/* Constructor */
public BinarySearchTree() {
root = null;
}
/* Functions to insert data */
public void add(String data) {
root = add(root, data);
}
/* Function to insert data recursively */
private Node add(Node node, String data) {
if (node == null)
node = new Node(data);
else {
if (data.compareTo(node.getData()) == -1)
node.left = add(node.left, data);
else
node.right = add(node.right, data);
}
return node;
}
/* Functions to search for an element */
public boolean contains(String s) {
return search(root, s);
}
/* Function to search for an element recursively */
private boolean search(Node r, String val) {
boolean found = false;
while ((r != null) && !found) {
String rval = r.getData();
if (val.compareTo(rval) == -1){
r = r.getLeft();
found = search(r, val);
}else if (val.compareTo(rval) == 1){
r = r.getRight();
found = search(r, val);
}else if(val.compareTo(rval) == 0){
found = true;
break;
}else{
found = false;
break;
}
}
return found;
}
public void display() {
display(root);
}
private void display(Node r) {
if (r != null) {
display(r.getLeft());
System.out.print(r.getData() + " ");
display(r.getRight());
}
}
}
/* Class BinarySearchTree */
public class TreeSpellChecker {
private BinarySearchTree bst = null;
public TreeSpellChecker(BinarySearchTree bst) {
this.bst = bst;
}
public BinarySearchTree getBinarySearchTree() {
return this.bst;
}
public static void comparTo(String val, String rval) {
if (val.compareTo(rval) == -1) {
System.out.println(" -1 ");
} else if (val.compareTo(rval) == 1) {
System.out.println(" 1 ");
} else if (rval.compareTo(val) == 0) {
System.out.println(" 0");
}
}
public static void main(String[] args) {
String fileName = "word-list";
TreeSpellChecker treeSpellchecker = new TreeSpellChecker(
new BinarySearchTree());
treeSpellchecker.readFileAndAddWordIntoTree(fileName);
System.out.println(treeSpellchecker.getBinarySearchTree().contains("zebra"));
treeSpellchecker.getBinarySearchTree().display();
TreeSpellChecker.comparTo("val1", "val");
}
public void readFileAndAddWordIntoTree(String fileName) {
List<String> wordList = TreeSpellChecker.readFile(fileName);
if (bst != null) {
for (String word : wordList) {
add(word);
}
}
}
public static List<String> readFile(String fileNameWithPath) {
List<String> list = new ArrayList<String>();
try (BufferedReader br = new BufferedReader(new FileReader(new File(
"d:\" + fileNameWithPath + ".txt")))) {
String sCurrentLine;
while ((sCurrentLine = br.readLine()) != null) {
list.add(sCurrentLine);
}
} catch (IOException e) {
e.printStackTrace();
}
return list;
}
public void add(String s) {
this.getBinarySearchTree().add(s);
}
public boolean contains(String s) {
return this.bst.contains(s);
}
}
class Node {
Node left, right;
String word;
/* Constructor */
public Node() {
left = null;
right = null;
word = null;
}
/* Constructor */
public Node(String n) {
left = null;
right = null;
word = n;
}
/* Function to set left node */
public void setLeft(Node n) {
left = n;
}
/* Function to set right node */
public void setRight(Node n) {
right = n;
}
/* Function to get left node */
public Node getLeft() {
return left;
}
/* Function to get right node */
public Node getRight() {
return right;
}
/* Function to set data to node */
public void setData(String d) {
word = d;
}
/* Function to get data from node */
public String getData() {
return word;
}
}
description :
1. As given in above question we have TreeSpellChecker.java class in above code whihc has following functions
A. void add(String s) Adds the specified word to the tree.
B. boolean contains(String s) Returns whether the specified word is in the trie.
C. void readFileAndAddWordIntoTree(String fileName) : A method that reads a list of words from a file and adds them all into the trie. In a trie, the order in which the words are added should not matter.
D. display to display all the words which are stored in tree.
There is main method in TreeSpellChecker.java which you need to execute to check the program behaviour. I hava taken one file name ( word-list) in d drive. you can change it as per your requirement.
File contents are :
john
stella
mark
su
cheng
ming
lee
rock
word
word1
word2
Output:
-----------
false // specified string not found that why it returned false
john rock stella lee mark su cheng ming word word1 word2 1 /// display the file contents or tree contents
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.