In java Write a program that uses a binary search tree to find out how many time
ID: 3693712 • Letter: I
Question
In java
Write a program that uses a binary search tree to find out how many times each word in a writing sample occurs. Your program should do the following: Read a text file. Build a binary search tree that uses data from the text file as it is read in: If the next word isn't in the tree, add it to the tree if the next word is in the tree, increment its count Print a word frequency histogram Input: This sentence repeats words because a sentence that repeats words makes a good example sentence. Output: a 2 because 1 example 1 good 1 makes 1 repeats 2 sentence 3 that 1 this 1 words 2Explanation / Answer
The following program reads each word from a file and builds a Binary Search Tree and then counts the frequency of each word from a file and prints..
import java.io.*;
import java.util.Scanner;
public class Driver {
public static void main(String[]args) throws IOException
{
//Checks if there is a correct number of arguments passed through the command line.
if (args.length != 1)
{
quitError("Tree command word arguments expected");
}
String inputFile = args[0];
BST btree = new BST();
try
{
BufferedReader input = new BufferedReader(new FileReader(inputFile));
//Scans each word from the input and prints it out
String word = input.readLine();
while (word != null)
{
btree.insert(word);
word = input.readLine();
}
return;
} catch(FileNotFoundException filenotfoundexception) //Catches file not found exception
{
System.out.println("File not found.");
}
catch(IOException ioexception) //Catches input/output exception
{
System.out.println("File input error occured!");
}
System.out.println(“Frequency of word in a BST “ + btree.count());
}
}
// Creating a node in BST..
public class BSTNode {
protected String data;
protected int value = 0;
protected BSTNode left, right;
public BSTNode()
{
left = null;
right = null;
}
public BSTNode(String data)
{
this(data,null,null);
}
public BSTNode(String data, BSTNode lt, BSTNode rt)
{
this.data = data;
left = lt;
right = rt;
}
}
// Code for the binary search tree:
public class BST {
protected BSTNode root = null;
public BST(){}
public void clear()
{
root = null;
}
public boolean isEmpty()
{
return root == null;
}
}
public void insert(String data)
{
BSTNode p = root, prev = null;
while (p != null) {
prev = p;
if (p.data.compareTo(data) < 0)
p = p.right;
else if(p.data.compareTo(data)>0)
p = p.left;
else p.value++;
}
if (root == null)
root = new BSTNode(data);
else if (prev.data.compareTo(data) < 0)
prev.right = new BSTNode(data);
else prev.left = new BSTNode(data);
}
public void inorder()
{
inorder(root);
}
private void inorder(BSTNode p)
{
if (p != null)
{
inorder(p.left);
System.out.print(p.data + " ");
inorder(p.right);
}
}
Public int count()
{
String inputFile = args[0];
BST btree = new BST();
try
{
BufferedReader input = new BufferedReader(new FileReader(inputFile));
//Scans each word from the input and prints it out
String word = input.readLine();
while (word != null)
{
BSTNode p = root, prev = null;
while (p != null) {
prev = p;
if (p.data.compareTo(word) < 0)
p = p.right;
else if(p.data.compareTo(word)>0)
p = p.left;
else System.out.println(word + “ “ +p.value);
}
}
return;
} catch(FileNotFoundException filenotfoundexception) //Catches file not found exception
{
System.out.println("File not found.");
}
catch(IOException ioexception) //Catches input/output exception
{
System.out.println("File input error occured!");
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.